acwing算法提高之图论--SPFA找负环

1 介绍

本专题用来记录使用spfa算法来求负环的题目。

2 训练

题目1：904虫洞

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;typedef pair<int, int> PII;const int N = 510;
int n, m, w;
int dist[N], cnt[N];
bool st[N]; //st[i]表示结点i是否在队列中
vector<vector<PII>> g;void spfa() {queue<int> q;for (int i = 1; i <= n; ++i) {q.push(i);st[i] = true;}while (!q.empty()) {auto t = q.front();q.pop();st[t] = false;for (auto [b, w] : g[t]) {if (dist[b] > dist[t] + w) {dist[b] = dist[t] + w;cnt[b] = cnt[t] + 1;if (!st[b]) {q.push(b);}if (cnt[b] >= n) {cout << "YES" << endl;return;}}}}cout << "NO" << endl;return;
}int main() {int T;cin >> T;while (T--) {cin >> n >> m >> w;g.clear();g.resize(n + 10);for (int i = 0; i < m; ++i) {int a, b, c;cin >> a >> b >> c;g[a].emplace_back(b, c);g[b].emplace_back(a, c);}for (int i = 0; i < w; ++i) {int a, b, c;cin >> a >> b >> c;g[a].emplace_back(b, -c);}memset(cnt, 0, sizeof cnt);spfa();}return 0;
}

题目2：361观光奶牛

01分数规划！

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;typedef pair<int, double> PID;const int N = 1010, M = 5010;
int n, m;
double v[N];
double dist[N];
int cnt[N];
bool st[N];struct Edge {int a, b;double w;
}edges[M];vector<vector<PID>> g;bool check(double mid) {g.clear();g.resize(n + 10);for (int i = 1; i <= n; ++i) { //初始化相关数组st[i] = false;cnt[i] = 0;dist[i] = 0.0;}for (int i = 0; i < m; ++i) {int a = edges[i].a, b = edges[i].b;double w = edges[i].w;//结点的权重加入到出边上w = mid * w - v[a];g[a].emplace_back(b, w);}queue<int> q;for (int i = 1; i <= n; ++i) {q.push(i);st[i] = true;}while (!q.empty()) {auto a = q.front();q.pop();st[a] = false;for (auto [b, w] : g[a]) {if (dist[b] > dist[a] + w) {dist[b] = dist[a] + w;cnt[b] = cnt[a] + 1;if (!st[b]) {q.push(b);}if (cnt[b] >= n) {return true;}}}}return false;
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> v[i]; //每个结点的权重for (int i = 0; i < m; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;} double l = 0, r = 1000;while (abs(l - r) > 1e-8) {double mid = (l + r) / 2.0;if (check(mid)) {//true,存在图中存在一个环使得比值大于midl = mid;} else {r = mid;}//cout << "l = " << l << ", r = " << r << endl;}printf("%.2lf", l);return 0;
}

题目3：1165单词环

C++代码如下，

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