之前觉得自己写的负环不是很好，今天想再写一遍。

负环

 负环，又叫负权回路，负权环，指的是一个图中存在一个环，里面包含的边的边权总和$<0$。在存在负环的图中，是求不出最短路径的，因为只要在这个环上不停的兜圈子，最短路径就会无限小。

 定理：如果一个点的入队的次数大于点的总数$N$，则存在负权回路。
 若图中没有负环，则最多经过$n-1$轮迭代后算法结束。所以若第$n$轮迭代仍有结点的最短路能被更新，则图中有负环。
 所以我们用$cnt[x]$表示$1$到$x$的最短路包含的边数（该题要求以$1$作为源点），$cnt[1]=0$。每次用 $dis[x]+w(x,y)$更新$dis[y]$时，也是$cnt[x]+1$更新 $cnt[y]$。此过程中若出现$cnt[y]\ge n$，则图中有负环。最坏情况复杂度也是$O(nm)$。

 参考代码

#include
#define in read()
#define MAXN 3003
#define MAXM 2*MAXN
using namespace std;
int T,n,m;
int nex[MAXM],first[MAXM],to[MAXM],val[MAXM],tot=0;
bool vis[MAXN];
int cnt[MAXN],dis[MAXN]; 
queue<int>q;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0' or c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' and c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}

inline void addedge(int u,int v,int w){//建图
	nex[++tot]=first[u];
	first[u]=tot;
	to[tot]=v;
	val[tot]=w;
}

inline void prework(){//初始化
	memset(first,0,sizeof(first));
	memset(to,0,sizeof(to));
	memset(nex,0,sizeof(nex));
	memset(val,0,sizeof(val));
	tot=0;
}

inline bool spfa(){//spfa求负环
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f3f,sizeof(dis));//初始化距离为极大值
	memset(cnt,0,sizeof(cnt));
	dis[1]=0;vis[1]=true;
	q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();//取出队首元素并出队
		vis[u]=false;//标记节点不在队列之中
		for(int e=first[u];e;e=nex[e]){
			int v=to[e];
			if(dis[v]>dis[u]+val[e]){
				dis[v]=dis[u]+val[e];
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)return true;//判断是否为负环
				if(!vis[v]){
					q.push(v);//入队
					vis[v]=true;//标记节点在队列之中
				}
			}
		}
	}
	return false;
}

int main(){
	T=in;
	while(T--){
		prework();
		n=in;m=in;
		for(int i=1;i<=m;i++){
			int u=in,v=in,w=in;
			addedge(u,v,w);
			if(w>=0)addedge(v,u,w);
		}
		if(spfa())cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

推荐练习：
 1.P3305[模板]负环
 2.P2850 [USACO06DEC]Wormholes G

 顺便把差分约束也学了把

差分约束系统(好玄学)

 差分约束系统是一种特殊的$n$元一次不等式组，它包含$n$个变量$x_1,x_2,x_3,...,x_n$以及$m$个约束条件，每个约束条件是由两个其中的变量做差构成的，形如$x_i-x_j\le c_k$，其中$1\le i,j\le n,i不等于j,1\le k\le m$并且$c_k$是常数（可以是非负数也可以是负数）。我们要解决的问题是：求一组解$x_1=a_1,x_2=a_2,...,x_n=a_n$ ，使得所有的约束条件得到满足，否则判断出无解。

 差分约束系统中的每个约束条件$x_i-x_j\le c_k$都可以变形成$x_i\le x_j+c_k$，这与单源最短路中的三角形不等式$di{s}_y\le di{s}_x+val(x,y)$非常相似。因此，我们可以把每个变量$x_i$看做图中的一个结点，对于每个约束条件$x_i-x_j\le c_k$，从结点$j$向结点$i$连一条长度为$c_k$的有向边。

 注意到，如果$a_1,a_2,a_3,...,a_i$是该差分约束系统的一组解，那么对于任意的常数$d$， $a_1+d,a_2+d,a_3+d,...,a_i+d$显然也是该差分约束系统的一组解，因为这样做差后$d$刚好被消掉。

 设$di{s}_0=0$并向每一个点连一条权重为$0$边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，$x_i=di{s}_i$为该差分约束系统的一组解。

 一般使用$SPFA$判断图中是否存在负环，最坏时间复杂度为$O(nm)$。

 参考代码

#include
#define in read()
#define MAXM 20005
#define re register
using namespace std;

bool vis[MAXM];
int cnt[MAXM],dis[MAXM];
int n,m;
int nex[MAXM],first[MAXM],to[MAXM],val[MAXM],tot=0;
queue<int>q;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}

inline void addedge(int u,int v,int w){
	nex[++tot]=first[u];
	first[u]=tot;
	to[tot]=v;
	val[tot]=w;
}

inline bool spfa(int st){
	for(re int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
	q.push(st),dis[st]=0,vis[st]=1;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int e=first[u];e;e=nex[e]){
			int v=to[e];
			if(dis[v]>dis[u]+val[e]){
				dis[v]=dis[u]+val[e];
				if(!vis[v]){
					cnt[v]=cnt[u]+1;
					if(cnt[v]>n+1)return true;
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return false;
}

int main(){
	n=in,m=in;
	for(re int i=1;i<=m;i++){
		int x=in,y=in,k=in;
		addedge(y,x,k);
	}
	for(re int i=1;i<=n;i++)
		addedge(0,i,0);
	if(spfa(0))cout<<"NO"<<'\n';
	else{
		for(re int i=1;i<=n;i++)
		cout<<dis[i]<<" "; 
	} 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

推荐练习：
 1.P5960 【模板】差分约束算法
 2.P1260 工程规划