前言

有一天，我正在做这道题目，做法就不讲了，在判负环的时候（当然这道题目0环也要判，后面再讲），我引发除了对SPFA这个队列优化的经过的边数的深入疑惑。

由于队列优化中已经插入的点不再插入，所以，这个会导致队列中的点的层数无法呈现阶段性增长，可能会导致判负环的时候经过的边数出一点问题，但在今天的思考中，我终于是证明不会有影响了。

首先讲讲如何判负环（有向图）吧，因为上篇浅谈SPFA中讲到，一个正常的SPFA路径最多只有(n-1)条边，超过就是存在负环了（经过一个点两次以上）。那么只需要记录一个(dep)（最短路经过的边数）即可。

当然，可能会有人有疑惑，为什么一个环的总和是负数，就一定不会断开更新，而是会一直更新下去呢？如果中间存在一个很大的正数呢？

考虑环上的点：(a_1,a_2,a_3...a_k)，首先这些点肯定会有一个点加入队列（不然就不是联通的了），然后对于(dis_{a_1}+b_1)（(b_1)为(a_1)至(a_2)的边），如果不能更新(a_2)，那么(dis_{a_2}<dis_{a_{1}}+b_1)（此时(a_2)是由外面的点扔进队列的），更新了就是(=)（此时的(a_2)是由(a_1)扔进队列的），反正只要(a_1)更新完之后，(a_2)都必然已经完成了其的任务或者是在队列里面（因为如果(a_2)是由外面的点扔进来的话，可能先于(a_1)更新的），而且因为(dis_{a_2}<dis_{a_{1}}+b_1)，(a1)能够更新的点，(a_2)也可以更新，然后用(a_2)证明(a_3)，不断证明下去，因为是负环，所以(a_n)最终会更新(a_1)（因为(a_1)能够更新(a_1)），然后不断这样更新下去，就断不了了。

回归本源，来讲讲为什么这个乱七八糟的(dep)为什么不会影响判断。

替代做法

如果你不想看这个做法跳了就行。

在此，给出一个减少了优化程度（但减少了修正的操作，本身也加大了一点优化程度，但是减少的应该更多吧），但是能更加直观的看到正确性的做法。

上次我们讲到其实存在了就不插入，本身是用前面代替后面，并等待修正，但是如果我们用后面代替前面的，如果已知后面存在新的(dis_x)，就不找这个点了，这样(list)里面的(dep)是呈现阶段性的，而且由于最多存在两种不同的(dep)（因为阶段性），所以最多有两个(x)在队列中（而且可以保证当(x)被取出队列时，当前的(dis_x)对于(dep_x)而言绝对是最小的）。

这样的话其实真的就是普通优化的表面否的算法了，但是更加的直观，不是吗？

#include<cstdio>
#include<cstring>
#define  N  2100
#define  NN  4100
#define  M  6100
using  namespace  std;
int  n,nn,m;
struct  STD_EDGE
{
	int  x,y,c;
}st[M];
struct  node
{
	int  y,next;double  c;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y,double  c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}

int  list[NN],head,tail,dep[N],v[N];
double  dis[N];
bool  check(double  val)
{
	len=0;memset(last,0,sizeof(last));
	for(int  i=1;i<=m;i++)ins(st[i].x,st[i].y,st[i].c*val);
	for(int  i=1;i<=n;i++)ins(st[i+m].x,st[i+m].y,-st[i+m].c);
	for(int  i=nn;i>=1;i--)dep[i]=0,dis[i]=999999999.0,v[i]=0;
	head=1;tail=2;list[1]=1;v[1]=1;dis[1]=0;
	//重点
	while(head!=tail)
	{
		int  x=list[head++];if(head==2*nn+1)head=1;
		if(dep[x]>=nn)return  1;
		v[x]--;if(v[x])continue;//后面存在一个x可以更新的更快 
		for(int  k=last[x];k;k=a[k].next)
		{
			int  y=a[k].y;
			if(dis[x]+a[k].c<=dis[y])
			{
				dis[y]=dis[x]+a[k].c;
				if(dep[x]>=dep[y])
				{
					dep[y]=dep[x]+1;v[y]++;
					list[tail++]=y;if(tail==2*nn+1)tail=1;
				}
			}
		}
	}
	//
	return  0;
}
int  main()
{
	scanf("%d%d",&n,&m);nn=n<<1;
	for(int  i=1;i<=n;i++)
	{
		int  x;scanf("%d",&x);
		st[m+i].x=i*2-1;st[m+i].y=i<<1;st[m+i].c=x;
	}
	for(int  i=1;i<=m;i++){scanf("%d%d%d",&st[i].x,&st[i].y,&st[i].c);st[i].x*=2;st[i].y=st[i].y*2-1;}
	double  l=1e-2,r=20,mid,ans;
	while(r-l>=1e-4)
	{
		mid=(l+r)/2;
		if(check(mid)==1)ans=mid,l=mid;
		else  r=mid;
	}
	printf("%.2lf
",ans);
	return  0;
}

当然你直接用表面否的也是没有问题的啦。

探究正常做法的正确性

仔细的思考，我们其实可以发现，我们不能把目光放到(dep)上面，而是放到更新上面，如果存在一条路径：(x->...->x)，不管其是不是对的，都至少说明存在一个环可以重复更新(x)，那么就是存在环的。

证毕。

当然，对于(dep)的记录，你需要明白：
对于相同长度的路径而言，我们可以记录任意一个(dep)，反正只要是最短路就可以了，不难发现，不管是存在还是不存在负环，记录任何的(dep)都不会影响判断。

如果要判断(0)环只需要把更新条件从(<)改成(≤)即可，证法不变（如果你还是不能理解，我们对于每条边加一个无限接近于0的负数，作为偏移量，这样就是求负环了吗，而且作用等价于(≤)）。

#include<cstdio>
#include<cstring>
#define  N  2100
#define  NN  4100
#define  M  6100
using  namespace  std;
int  n,nn,m;
struct  STD_EDGE
{
	int  x,y,c;
}st[M];
struct  node
{
	int  y,next;double  c;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y,double  c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}

int  list[NN],head,tail,dep[N],v[N];
double  dis[N];
bool  check(double  val)
{
	len=0;memset(last,0,sizeof(last));
	for(int  i=1;i<=m;i++)ins(st[i].x,st[i].y,st[i].c*val);
	for(int  i=1;i<=n;i++)ins(st[i+m].x,st[i+m].y,-st[i+m].c);
	for(int  i=nn;i>=1;i--)dep[i]=0,dis[i]=999999999.0,v[i]=0;
	head=1;tail=2;list[1]=1;v[1]=1;dis[1]=0;
	//重点
	while(head!=tail)
	{
		int  x=list[head++];if(head==nn+1)head=1;
		if(dep[x]>=nn)return  1;
		v[x]=0;
		for(int  k=last[x];k;k=a[k].next)
		{
			int  y=a[k].y;
			if(dis[x]+a[k].c<=dis[y])
			{
				dis[y]=dis[x]+a[k].c;
				dep[y]=dep[x]+1;
				if(!v[y])
				{
					v[y]=1;
					list[tail++]=y;if(tail==nn+1)tail=1;
				}
			}
		}
	}
	//
	return  0;
}
int  main()
{
	scanf("%d%d",&n,&m);nn=n<<1;
	for(int  i=1;i<=n;i++)
	{
		int  x;scanf("%d",&x);
		st[m+i].x=i*2-1;st[m+i].y=i<<1;st[m+i].c=x;
	}
	for(int  i=1;i<=m;i++){scanf("%d%d%d",&st[i].x,&st[i].y,&st[i].c);st[i].x*=2;st[i].y=st[i].y*2-1;}
	double  l=1e-2,r=20,mid,ans;
	while(r-l>=1e-4)
	{
		mid=(l+r)/2;
		if(check(mid)==1)ans=mid,l=mid;
		else  r=mid;
	}
	printf("%.2lf
",ans);
	return  0;
}

扩展

假如我们按照常规的SPFA做，然后在更新的时候同时更新(dep)（表示最短路径经过的边数）那么会有以下性质（接下来的(dis[dep_x][x])表示经过(dep_x)条边时(dis_x)的值）：

重复修正
这里讲一下我所说的修正的定义，对于(dis[dep_x][x])，如果未来出现了(dis[dep_{x‘}][x]＜dis[dep_x][x](dep_{x'}≤dep_x))，并加入了队列，那么就称(x)被修正，但是一个(x)有可能被重复修正多次（想想就知道）。
不正确性

在(x)的时候出现了混乱，在上篇文章中讲到，这样子正确性并没有变，因为可以由后面的(dep)深度的点进行修正，重新产生(x)，也就是说，第一次产生的(dis[dep_x][x])不一定是最小的，但是最后一次一定是。
无法修正
如果深度小于等于(dep)的点在队列中完全消失了，那么意味着现在小于等于(dep+1)的(dis)都是最小的。
队列中最小的深度是(dep)，那么接下来不会再有(dep)深度的点插入进来
将(x)每次刚插入时的(dep)记录下来，不会有两个(dep)是相同的。

当然，上面的性质只是让你在用(dep)的时候更加的灵活罢了。