2018年5月27号（spfa判断负环）

　　一开始并不懂得真正判断负环，自从写了这道题才有点感觉：这道题就是洛谷的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）不停的做如果值变成了负数，就说明碰到了负环；同时可以用草稿本算一遍，你就可以立刻明白;

　　今天就说到这，这是我第一篇博客（请各位看官赏个脸）

Keep on going never give up. 　　勇往直前，决不放弃！