关于一个图中是否存在负环(更新版)

xiaoxiao2021-02-28  108

负环的判断

第一次写博客,表示心里很慌

我第一次接触负环的判断是在一道差分约束的题目里:点击打开链接

以下为假算法

说实话,这道题目其实是比较裸的判负环,但是很多人就卡在负环上,有的人会用dijkstra算法(因为dij的原理是贪心,当有负权环的时候它的贪心策略就不成立了,所以不行),有的人用SPFA,但是用的BFS,于是。。。光荣的TLE了,原因就在于在判断以及之后的退出上DFS比BFS更有力,所以要用DFS,那么具体的操作呢?

先来看看正常情况(单源最短路)下的bfs版SPFA:

 

//h[]初始化为INF void SPFA() { int he=0,t=1;//手写队列,虽然queue很好用,但我还是爱手写 h[st]=0;vis[st]=true; d[1]=st;//d[]就是队列数组 do{//这个循环干啥的应该都懂 he++; int p=d[he]; vis[p]=false; for(register int i=head[p];i!=-1;i=e[i].next)//我建图一般用前向星,vector版的应该是for(int j=0;j<e[sta].size();j++) { int v=e[i].to;//列举下一个节点 if(h[v]>h[p]+e[i].dis)//判断谁更短 { h[v]=h[p]+e[i].dis; if(!vis[v]){//是否访问过该节点 d[++t]=v;//没有则入队 vis[v]=true;//标记 } } } }while(he<t); } 那么这种算法在出现了负环的情况下会如何呢?

 

我们就以这个有点鬼畜的环为例,假设我们搜到了a节点,继续搜b节点,因为边权为负,所以h[a]更新,那么搜b、搜c、搜d时,因为边权都是负的,那么都会更新相应节点的h值,这个时候……我们搜回a节点了,将要发生的一切,似乎就顺理成章了,死循环到天荒地老……那么要如何避免呢?

 

如果你用BFS,那么判定的依据是一个点入队超过n次,这个复杂度足以让你绝望了,但是如果说是DFS,判断的依据就是多次被搜到,这个解决起来就方便多了,看一看代码:

struct node { int next; int to; int dis; }e[500010]; bool vis[500001],flag;//flag标记负环 void add(int u,int v,int w) { e[++tot].to=v; e[tot].next=head[u]; e[tot].dis=w; head[u]=tot; } void dfs(int sta) { vis[sta]=true; if (flag) return; for (int i=head[sta];i;i=e[i].next){ int v=e[i].to; if (h[sta]+e[i].dis<h[v]) { h[v]=h[sta]+e[i].dis; if (vis[v]){ flag=true; return; } else dfs(v); } } vis[sta]=false; return ; }

//主函数里的调用是for(int i=1;i<=n;i++){dfs(i);if(flag)  break;} 在这里有一个优化,原版的SPFA的h[]数组初始化时是赋的INF,一个极大的数,这在单源最短路是对的,但在判负环时反而会拖慢效率,所以不如把h[]初始化为0,那么只有出现负权边时才会更新并搜索,在发现负环后立马退出,极大的提升了效率,至于别的快读之类的优化就看你个人了。 有关负环我就讲这么多,推荐一些练习:洛谷P1993 P3385 poj3259  洛谷P2850

更新一下啊

学长讲的dfsSPFA貌似有道理,我就没有关注过正确性,然而事实证明dfs的复杂度存在很大的问题,不信您可以看看洛谷的[模板]负环,所以用bfs版的 比较好吧,dfs虽然在随机数据的情况下表现出色,但是鬼知道出题人是怎么出的数据……

丢一篇题解逃之夭夭

#include <bits/stdc++.h> //#define LOCAL using std::min; using std::max; using std::queue; const int MAXN = 10100; const int MAXE = 40000; const int INF = 0x7FFFFFFF; #define pb push_back #define mp make_pair #define Debug(...) fprintf(stderr, __VA_ARGS__) #define getchar() *S ++ char RR[3 * 1024 * 1024], *S = RR; template <typename T> inline void read(T &x) { int c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } struct Edge { int to, nxt, len; Edge() {} Edge(int _to, int _nxt, int _len) : to(_to), nxt(_nxt), len(_len) {} }E[MAXE]; int p, h[MAXN], vis[MAXN], d[MAXN], sum[MAXN]; int n, m, T; queue<int>q; inline void init() { p = 0; memset(h, 0, sizeof(h)); while(!q.empty()) q.pop(); } inline void add_edge(int u, int v, int w) { E[++p] = Edge(v, h[u], w), h[u] = p; } inline bool SPFA(int x) { memset(d, 0x3f, sizeof(d)); memset(vis, 0, sizeof(vis)); while(!q.empty()) q.pop(); vis[x] = 1; d[x] = 0; sum[x] = 0; q.push(x); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = h[u]; i; i = E[i].nxt) { int v = E[i].to; if(d[v] > d[u] + E[i].len) { d[v] = d[u] + E[i].len; sum[v] = sum[u] + 1; if(sum[v] >= n) return 1; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } return 0; } signed main() { fread(RR, 1, sizeof(RR), stdin); read(T); while(T --) { read(n), read(m); for(int i = 1, a, b, c; i <= m; i++) { read(a), read(b), read(c); add_edge(a, b, c); if(c >= 0) add_edge(b, a, c); } if(SPFA(1)) puts("YE5"); else puts("N0"); init(); } #ifdef LOCAL Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-34218.html

最新回复(0)