前言

血的教训：模拟赛出了个差分约束板子结果发现不会打。 题目链接

引入

我们有一些形如 \[x_c-x_{c^\prime}\le y\] 的方程构成了方程组，要求出一组解。 之后进行神奇的关联，我们来看一个求最短路的代码片段： 

1
2
3
4
5
6
7
if(dis[v]>dis[u]+e[i].w){
	dis[v]=dis[u]+e[i].w;
	if(!vis[v]){
		q.push(v);
		vis[v]=1;
	}
}
我们发现，这里通过松弛操作维护了 \[dis[v] \le dis[u]+e[i].w\] 移项，得 \[dis[v]-dis[u]\le e[i].w\] 我们发现，这与题目中所给的方程形式完全一致。所以，我们可以将解方程组转化为一个图论问题，使用最短路算法求出方程的一组解，这就是差分约束系统。 ###题目解法 通过观察以上两个式子，发现 \(c\) 对应一条边的 \(v\) 节点，\(c^\prime\) 对应边的 \(u\) 节点，只要建立一个权值为 \(y\) 的边就好了。 但我们发现，这样不一定能保证图的连通性，解决办法是建立一个虚拟的 \(0\) 号超级源点，与每个节点建一条权值为 \(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
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=5e3+10,M=1e4+10;
int n,m,head[N],tot,cnt[N];
long long dis[N];
struct edge{
	int to,nxt,w;
}e[M];
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].w=w;
	head[u]=tot;
	return;
}
bool vis[N];
queue<int> q;
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;
	q.push(0);
	vis[0]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
					cnt[v]++;
					if(cnt[v]==n+1)//判负环
						return 0;
				}
			}
		}
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		add(0,i,0);//虚拟源点
	for(int i=1;i<=m;i++){
		int c1,c2,y;
		scanf("%d%d%d",&c1,&c2,&y);
		add(c2,c1,y);
	}
	if(spfa()){
		for(int i=1;i<=n;i++)
			printf("%d ",dis[i]);
		return 0;
	}
	printf("NO");
	return 0;
}

其他形式

若有 \(x_c-x_{c^\prime}\ge y\)，可以两边同时乘 \(-1\) 改变不等号方向，或者跑最长路。 若有 \(x_c-x_{c^\prime}=y\)，可以将其拆分为 \[ \begin{cases} x_c-x_{c^\prime}\le y\\ x_c-x_{c^\prime}\ge y \end{cases} \] End.