前言

这个算是鸽了很久都没去学的算法。然后模拟赛考出来（我又不会并查集做法），所以在改题之前，还得先完成一下前置知识。

差分约束的前置知识

<Ⅰ>\(Spfa\)判断负环

【模板】负环

用\(Spfa\)判断入队次数是否\(≥n\)，如果是，说明有负环。感性理解一下，一个图上如果有负环，它会一直绕着负环跑，然后越来越小，越来越小……

\(code\):

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+105,M=6e3+105;
int n,m,h[N],nex[M],to[M],v[M],cnt,d[N],tot[N],T,x,y,z;
bool f[N];//v已经有了 
inline void add(int x,int y,int z){
	to[++cnt]=y;v[cnt]=z;
	nex[cnt]=h[x];h[x]=cnt;
}
bool spfa(){
	memset(f,0,sizeof(f));memset(d,0x3f,sizeof(d));memset(tot,0,sizeof(tot));
	queue<int>q;
	d[1]=0;f[1]=1;q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();f[x]=0;
		for(int i=h[x];i;i=nex[i])
			if(d[to[i]]>d[x]+v[i]){
				d[to[i]]=d[x]+v[i];
				if(!f[to[i]]){
					if(++tot[to[i]]>n) return 1;
					q.push(to[i]);f[to[i]]=1;
				}
			}
	}
	return 0;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);if(z>=0)add(y,x,z);
		}
		spfa()?puts("YES"):puts("NO");
		memset(h,0,sizeof(h));cnt=0;
	}
	return 0;
}

<Ⅱ> 定义

差分约束系统

给出\(n\)个变量（\(x_1,x_2,x_3……x_n\)），和 \(m\) 个 约束条件 （粗略理解为不等式，求一些满足约束条件的解。

假设给出一个这样的差分约束系统：
\(x_a-x_b ≤ k_1\)
\(x_a-x_c ≤ k_2\)
\(x_b-x_d ≤ k_3\)
\(x_d-x_c ≤ k_4\)

可以把它写成统一形式： \(x_i≤x_j+k\)

转化成图，大概是这样的：

如果要找\(x_a-x_d\)的最小值，即在图上跑点\(a\)到点\(d\)的最短路。

例题

【模板】差分约束算法

\(code\):