算法提高课-图论-负环-AcWing 904. 虫洞：spfa求负环裸题

文章目录

• • • 题目分析
    • 题目链接

题目分析

来源：acwing

分析：

负环：负环是这样的一个环，该环上的边权之和是负数。

存在负环的话，会对我们求最短路造成障碍，因为绕着这个负环转无数次，最短路越来越小，最后是－∞。

求负环的常见方法， 基于SPFA：

统计每个点入队的次数，如果某个点入队n次（说明某点被更新大于等于n次），则说明存在负环。

统计每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则说明有负环。（常用该法）

SPFA求负环的时间复杂度，经验值是$O(mn)$,所以可能会超时。这里有个取巧的方法：当所有点的入队次数超过2n(或者3n)时，我们就认为图中有很大可能是存在负环的。

AC代码

#include<bits/stdc++.h> using namespace std; const int N = 510, M = 5210; int n, m1, m2; int h[N], e[M], w[M], ne[M], idx; int 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 ++; }// spfa判断负环 bool spfa(){int hh = 0, tt = 0;memset(dist, 0, sizeof dist); // 距离可以初始化为任何值memset(st, 0, sizeof st); // 判重数组memset(cnt, 0, sizeof cnt); // 最短路包含的边数// 所有点压入队列，分析过程需要借助虚拟源点for(int i =1; i <= n; i ++){q[tt ++] = i;st[i] = true;}while(hh != tt){auto 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]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;// 以j为终点的最短路的边数// 如果边数≥n，说明存在负环if(cnt[j] >= n) return true;if(!st[j]){q[ tt++] = j;if(tt == N) tt = 0;st[j] = true;}}}}return false; }int main(){int T;cin >> T;while(T --){cin >> n >> m1 >> m2;memset(h, -1, sizeof h);idx = 0;while(m1 --){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}// 负权边while( m2 --){int a, b, c;cin >> a >> b >> c;add(a, b, -c);}if(spfa()) puts("YES");else puts("NO");}}

题目链接

https://www.acwing.com/problem/content/906/

总结

以上是生活随笔为你收集整理的算法提高课-图论-负环-AcWing 904. 虫洞：spfa求负环裸题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。