第一次写博客，表示心里很慌
我第一次接触负环的判断是在一道差分约束的题目里：点击打开链接
以下为假算法
说实话，这道题目其实是比较裸的判负环，但是很多人就卡在负环上，有的人会用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; }
