作者：涐們的故事丘 | 来源：互联网 | 2023-06-03 21:33
一开始并不懂得真正判断负环，自从写了这道题才有点感觉：这道题就是洛谷的p1768天路。我主要想说如何判断负环:首先一个最普通的做法：就是在做spfa的同时进行cnt++；利用cnt
一开始并不懂得真正判断负环，自从写了这道题才有点感觉：这道题就是洛谷的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）不停的做如果值变成了负数，就说明碰到了负环；同时可以用草稿本算一遍，你就可以立刻明白;
今天就说到这，这是我第一篇博客（请各位看官赏个脸）
京公网安备 11010802041100号