差分约束学习笔记

2023.5.6 写的太烂了重新写

差分约束系统

定义

差分约束系统是一种特殊的 (n) 元一次不等式组，它包含 (n) 个变量 (x_{1},x_{2},...,x_{n}) 以及 (m) 个约束条件，每一个约束条件都是两个其中的变量做差构成的，形如 (x_{i}-x_{j}le c_{k})，其中 (1le i,jle n,ine j,1le kle m) 并且 (c_{k}) 是常数（可以为正数或非正数）。
------- OI Wiki

通俗一点讲，这类问题都是给定 (n) 个变量，(m) 个限制，类似于：

[left{begin{matrix} op_{1}:x_{1}-x_{2}=c_{1}\ op_{2}:x_{4}-x_{n}=c_{2}\ ......\ op_{m}:x_{n}-x_{3}=c_{m} end{matrix}right. ]

有了这些条件，一般的题目会让你求出一组合法的解，也就是求这 (n) 个变量的合法的值。

过程

我们可以建一个超级源点，然后向每一个点连一条边权为 (0) 的边，然后跑单源最短路；而上面的 (m) 个限制都可以变形为 (x_{i}le x_{j}+c_{k})，这个东西很容易想到我们在跑最短路的时候的松弛操作里的 (dis[v]le dis[u]+w)，因此我们就可以把每一个变量看作是一个图中的点，对于每一个条件 (x_{i}-x_{j}le c_{k})，从 (j) 向 (i) 连一条边权为 (c_{k}) 的有向边。

我们在求解的时候一般用 SPFA 来跑，虽然他最坏的时间复杂度是 (O(nm)) 的，但是我们的差分约束里面要是有负环的话，就说明是无解，再加上有负边权，SPFA 这个已死的算法成了最好的方法，更何况他在一些随机的图中跑的飞快。

最后一个问题，最后转化的式子是 (x_{i}le x_{j}+c_{k})，为什么跑最短路？

但是我觉得，当你建图的时候使用的是 (x_{i}-x_{j}le c_{k}) 形式的方程组建图时，即 (j) 向 (i) 连一条权值为 (c_{k}) 的边，应该选择跑最短路。

如果使用的是 (x_{i}-s_{j}ge c_{k}) 形式的方程组来建图时，应该选择跑最长路。

P5960 【模板】差分约束算法

code:

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define N 50100 using namespace std; int n,m,cnt,head[N]; queue<int>q; struct SB{int w,v,next;}e[N<<1]; int dis[N],tot[N],vis[N]; inline void add(int u,int v,int w) { 	e[++cnt].v=v; 	e[cnt].w=w; 	e[cnt].next=head[u]; 	head[u]=cnt; } int SPFA() { 	 	q.push(0); 	vis[0]=1; 	tot[0]++; 	while(!q.empty()) 	{ 		int u=q.front(); 		q.pop(); 		vis[u]=0; 		for(int i=head[u];i;i=e[i].next) 		{ 			int v=e[i].v,w=e[i].w; 			if(dis[v]>dis[u]+w) 			{ 				dis[v]=dis[u]+w; 				q.push(v); 				vis[v]=1; 				tot[v]++; 				if(tot[v]==n+1) 				return 0; 			} 		} 	} 	return 1; } int main() { 	cin>>n>>m; 	for(int i=1;i<=n;i++) 	  dis[i]=INF; 	for(int i=1;i<=n;i++) 	  add(0,i,0); 	for(int i=1;i<=m;i++) 	{ 		int x,y,z; 		cin>>x>>y>>z; 		add(y,x,z); 	} 	if(!SPFA()) 	  cout<<"NO"<<endl; 	else 	  for(int i=1;i<=n;i++) 		cout<<dis[i]<<" "; 	return 0; }