图论——spfa判负环

负环

图$G$中存在一个回路，该回路边权之和为负数，称之为负环。

spfa求负环

方法1:统计每个点入队次数, 如果某个点入队n次, 说明存在负环。
证明：一个点入队n次，即被更新了n次。一个点每次被更新时所对应最短路的边数一定是递增的，也正因此该点被更新n次那么该点对应的的最短路长度一定大于等于n，即路径上点的个数至少为n+1。根据抽屉原理，路径中至少有一个顶点出现两次, 也就是路径中存在环路。 而算法保证只有距离减少才会更新, 所以环路权值之和为负数。

方法2:统计从起点到任意顶点最短路经过的边数, 若某点对应边数$cnt\ge n$, 则也说明负环。
方法2根据抽屉原理易证。
我们一般采用方法2才求负环。

acwing904.虫洞

spfa求负环模板题

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 5210;
int h[N], w[M], e[M], ne[M], tot;
int dist[N];
int cnt[N];
bool st[N];
int q[N];
int t;
int n, m, k;
void add(int a, int b, int c)
{e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool spfa()
{memset(dist, 0, sizeof dist);memset(st, 0, sizeof st);memset(cnt, 0, sizeof cnt);int hh = 0, tt = 0;for (int i = 1; i <= n; i ++ ){st[i] = 1;q[tt ++ ] = i;}while (hh != tt){int t = q[hh ++ ];if (hh == N) hh = 0;st[t] = 0;for (int i = h[t]; ~i; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;if (cnt[j] == n) return true;if (st[j]) continue;st[j] = 1;q[tt ++ ] = j;if (tt == N) tt = 0;}}}return false;
}
int main()
{cin >> t;while (t -- ){cin >> n >> m >> k;tot = 0;memset(h, -1, sizeof h);while (m -- ){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}while (k -- ){int a, b, c;cin >> a >> b >> c;add(a, b, -c);}bool t = spfa();if (t) puts("YES");else puts("NO");}return 0;
}

acwing361.观光奶牛

本题要求我们求出环中存在的$\frac{\sum f[i]}{\sum t[i]}$的最大值，如果直接对问题进行求解是有难度的，考虑二分答案。首先易知，答案的范围在$[1/1000,1000]$之间，假设我们当前二分到的答案为$mid$,如果$ans<mid$,我们可以去左半区间进行寻找,反之我们去右半区间寻找。
$$\frac{\sum f[i]}{\sum t[i]}>mid$$
$$\sum f[i]>mid\ast \sum t[i]$$
$$\sum f[i]-mid\ast \sum t[i]>0$$
$$\sum (f[i]-mid\ast t[i])>0$$
$$\sum (mid\ast t[i]-f[i])<0$$
经过转换后，问题就等价于把图中边权换为$mid\ast t[i]-f[i]$,然后判断图中是否存在负环，存在负环则说明图中存在$\frac{\sum f[i]}{\sum t[i]}>mid$的环。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 5010;
int h[N], e[M], ne[M], tot;
int wf[N], wt[M];
int q[N];
double dist[N];
int cnt[N];
bool st[N];
int n, m;
void add(int a, int b, int c)
{e[tot] = b, ne[tot] = h[a], wt[tot] = c, h[a] = tot ++ ;
}
bool check(double x)
{memset(dist, 0, sizeof dist);memset(st, 0, sizeof st);memset(cnt, 0, sizeof cnt);int hh = 0, tt = 0;for (int i = 1; i <= n; i ++ ){st[i] = 1;q[tt ++ ] = i;}while (hh != tt){int t = q[hh ++ ];if (hh == N) hh = 0;st[t] = 0;for (int i = h[t]; ~i; i = ne[i]){int j = e[i];double w = x * wt[i] - wf[t];if (dist[j] > dist[t] + w){dist[j] = dist[t] + w;cnt[j] = cnt[t] + 1;if (cnt[j] == n) return true;if (st[j]) continue;st[j] = 1;q[tt ++ ] = j;if (tt == N) tt = 0;}}}return false;
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ )cin >> wf[i];memset(h, -1, sizeof h);for (int i = 1; i <= m; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}double l = 0, r = 1001;while (r - l > 1e-4){double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}printf("%.2lf", l);return 0;
}

acwing1165.单词环

我们第一感觉是把每一个单词看作一个节点，这样一来节点总数$n=10^5$，最坏情况是所有单词都可以互相进行匹配，这样一来边数$m=10^5\ast 10^5=10^{10}$，考虑其他建图方式。
我们可以把每个单词看作一条边，这样一来边数$m=10^5$,每个单词开头结尾两个字母为节点，节点总数$n=26\ast 26=676$。
本题要求我们求所有环的$\frac{\sum w[i]}{\sum 1}$最大值。和上题相同，二分答案，答案区间为$[1/1000,1000]$。
$$\frac{\sum w[i]}{\sum 1}>mid$$
$$\sum w[i]>mid$$
$$\sum w[i]-mid>0$$
$$\sum (w[i]-mid)>0$$
$$\sum (mid-w[i])<0$$
经过转换后，问题就等价于把图中边权换为$mid-w[i]$,然后判断图中是否存在负环，存在负环则说明图中存在$\frac{\sum w[i]}{\sum 1}>mid$的环。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 26 * 26 + 10, M = 100010;
int h[N], e[M], ne[M], w[M], tot;
double dist[N];
bool st[N];
int cnt[N];
int q[N];
char s[1010];
int n;
void add(int a, int b, int c)
{e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool check(double mid)
{memset(st, 0, sizeof st);memset(dist, 0, sizeof dist);memset(cnt, 0, sizeof cnt);int hh = 0, tt = 0;for (int i = 0; i < 26 * 26; i ++ ){q[tt ++ ] = i;st[i] = 1;}int count = 0;while (hh != tt){int t = q[hh ++ ];st[t] = 0;if (hh == N) hh = 0;for (int i = h[t]; ~i; i = ne[i]){int j = e[i];double ww = mid - w[i];if (dist[j] > dist[t] + ww){dist[j] = dist[t] + ww;cnt[j] = cnt[t] + 1;if (++ count == 10000) return true;if (cnt[j] == N) return true;if (st[j]) continue;st[j] = 1;q[tt ++ ] = j;if (tt == N) tt = 0;}}}return false;
}
int main()
{while (cin >> n, n){memset(h, -1, sizeof h);tot = 0;for (int i = 1; i <= n; i ++ ){cin >> s;int len = strlen(s);if (len < 2) continue;int ll = (s[0] - 'a') * 26 + s[1] - 'a';int rr = (s[len - 2] - 'a') * 26 +s[len - 1] - 'a';add(ll, rr, len);}double l = 0, r = 1001;if (!check(0)) puts("No solution");else{while (r - l > 1e-4){double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}printf("%.2lf\n", r);}}return 0;
}