一开始并不懂得真正判断负环，自从写了这道题才有点感觉：这道题就是洛谷的p1768天路。
我主要想说如何判断负环:
首先一个最普通的做法：
1 void spfa(int x) 2 { 3 vis[x]=true; 4 for(int i=head[x];i;i=e[i].next) 5 { 6 if(dis[e[i].to]>dis[x]+e[i].dis) 7 { 8 cnt++; 9 if(cnt>=n) 10 { 11 flag=1; 12 return ; 13 } 14 dis[e[i].to]=dis[x]+e[i].dis; 15 spfa(e[i].to); 16 } 17 } 18 vis[x]=false; 19 }
就是在做spfa的同时进行cnt++；利用cnt这个计数器来计算apfa的次数，如果次数大于等于了数的总数n；那么说明这个spfa做到了下一个轮回，这就说明碰到了负环；那么就可以结束循环，做个标记，输出出现负环的提示。
接下来再使计数器优化一下，看书之后就有了这样做法：
1 void spfa(int x) 2 { 3 vis[x]=true; 4 for(int i=head[x];i;i=e[i].next) 5 { 6 if(dis[e[i].to]>dis[x]+e[i].dis) 7 { 8 pd[e[i].to]=pd[x]+1;//只是这里改变了一下，由cnt改成数组存； 9 if(e[i].to>=n) 10 { 11 flag=1; 12 return ; 13 } 14 dis[e[i].to]=dis[x]+e[i].dis; 15 spfa(e[i].to); 16 } 17 } 18 vis[x]=false; 19 }
其实这个代码跟上面一个差不多
就是将spfa函数里的cnt计时器改成数组来存，这样边存入边计算，使时间节省很多，入过你TLE了可以使用这种方法；反正我屡用不爽
还有一种会比较高级，一开始我也没有反应过来（据说时间更快，不过我没有用它和第二个做实验），但蒟蒻的我没有反应过来
话不多说 呈上代码：
1 bool zx(int x,double nj) 2 { 3 vis[x]=1; 4 for(int i=h[x];i;i=e[i].nx) 5 { 6 double p=1.0*e[i].p*nj-1.0*e[i].v; 7 if(p+ans[x]<ans[e[i].to]) 8 { 9 ans[e[i].to]=p+ans[x]; 10 if(vis[e[i].to]||zx(e[i].to,nj))//就这个zx(e[i].to,nj)，利用了深搜来解决一切 11 { 12 vis[e[i].to]=0; 13 return 1; 14 } 15 } 16 } 17 vis[x]=0; 18 return 0; 19 }
其实这点还好理解，及你有许多的数时，做起这个spfa时，zx（e[i].to,nj）不停的做如果值变成了负数，就说明碰到了负环；同时可以用草稿本算一遍，你就可以立刻明白;
今天就说到这，这是我第一篇博客（请各位看官赏个脸）
原文：https://www.cnblogs.com/zssmg/p/9098093.html