【差分约束】学习笔记

Basic Tips

差分约束，即为存在一个差分约束系统，即类似 \(x_i - x_j \leq k\) 的 \(n\) 元一次不等式组，求出一组解使得该组内所有不等式全部成立，即 \(x_1 = s_1,x_2 = s_2 \dots x_n = s_n\)，否则判无解。

对于满足条件的一个解集 \(\{s_1,s_2,s_3,\dots,s_n\}\)，集合 \(\{s_1 + t,s_2 + t,s_3 + t,\dots,s_n + t\}\) 也满足成为解集的条件。

为何用 spfa 求解？

名副其实，对于每一个不等式 \(x_i - x_j \leq k\)，移项可得 \(x_i \leq x_j + k\)，与 \(\text{spfa}\) 中的三角不等式极其相似，因此可以看做是 \(x_j\) 向 \(x_i\) 连了一条边权为 \(k\) 的有向边，然后就可以用 \(\text{spfa}\) 求解，若过程中存在负环则差分约束系统无解，否则对于 \(s_i = dis_i\) 即为差分约束系统的一个解。

注：\(\text{spfa}\) 跑最长路还是最短路的情况依据推出的差分约束系统不等式的形式，若为 \(x_i - x_j \leq k\)，我们选择最短路，若 \(x_i - x_j \geq k\)，我们选择最长路。

other

\(\text{spfa}\) 中的三角不等式 \(disv \geq dis_u + w\) 的解释。

如图：

\(v\) 为终点，\(u\) 为起点，\(v1\) 为中转点，显然，\(u \to v1 \to v\) 的路径是比 \(u \to v\) 的路径长的，因此 \(\text{spfa}\) 的过程可以看成对于每个点的出边做一次这样的操作。

example

P5960 【模板】差分约束

差分约束模板，根据上文所说的过程实现就行，需要注意的是，在没有保证建出的图联通时，需要从超级源点向每一条点连边。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e3 + 10;
int n,m,idx=1,head[MAXN << 1];
int dist[MAXN << 1],cnt[MAXN << 1];
bool vis[MAXN << 1];
struct node{
	int v,w,nxt;
}edge[MAXN << 1];
inline void add(int u,int v,int w){
	edge[idx].v = v;
	edge[idx].w = w;
	edge[idx].nxt = head[u];
	head[u] = idx ++;
}
inline bool spfa(int s){
	memset(cnt,0,sizeof cnt);
	memset(dist,-0x3f,sizeof dist);
	memset(vis,0,sizeof vis);
	queue<int>q;
	vis[s] = 1;
	dist[s] = 0;
	q.push(s);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i=head[u];i!=-1;i=edge[i].nxt){
			int v = edge[i].v,w = edge[i].w;
			if(dist[v] < dist[u] + w){
				dist[v] = dist[u] + w;
				if(!vis[v]){
					cnt[v] = cnt[u] + 1;
					if(cnt[v] > n + 1)
						return false;
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return true;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	memset(head,-1,sizeof head);
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		add(u,v,-w);
	}
	for(int i=1;i<=n;i++)
		add(0,i,0);
	if(!spfa(0))
		cout << "NO" << endl;
	else{
		for(int i=1;i<=n;i++)
			cout << dist[i] << " ";
		cout << endl;
	}
	return 0;
} 

P4878 [USACO05DEC] Layout G

依据题目中给出的条件列出不等式 。

\( \begin{cases} x_i - x_j \leq d1 \\ x_k - x_p \geq d2 \end{cases} \)

然后建边，由于全图不保证联通，因此需要超级源点，从超级源点跑一次 \(\text{spfa}\) 判无解，另外从 \(1\) 号节点跑统计答案，由于题目中默认条件 \(x_i < x_j(i > j)\)，需要将相邻两点连边。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e4 + 10;
const int inf = 1e9;
int n,m1,m2,idx = 1,head[MAXN],dis[MAXN],cnt[MAXN];
bool vis[MAXN];
struct node{
	int v,nxt,w;
}edge[MAXN];
inline void add(int u,int v,int w){
	edge[idx].v = v;
	edge[idx].w = w;
	edge[idx].nxt = head[u];
	head[u] = idx ++;
}
inline int spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	queue<int>q;
	dis[s] = 0;
	vis[s] = 1;
	q.push(s);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		cnt[u] ++;
		if(cnt[u] > n)
			return -1;
		for(int i = head[u];i != -1;i = edge[i].nxt){
			int v = edge[i].v,w = edge[i].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				if(!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	if(dis[n] > inf)
		return -2;
	return dis[n];
}
signed main(){
	memset(head,-1,sizeof(head));
	scanf("%lld %lld %lld",&n,&m1,&m2);
	for(int i = 1;i <= m1;i ++){
		int u,v,w;
		scanf("%lld %lld %lld",&u,&v,&w);
		add(u,v,w);
	}
	for(int i = 1;i <= m2;i ++){
		int u,v,w;
		scanf("%lld %lld %lld",&u,&v,&w);
		add(v,u,-w);
	}
	for(int i = 1;i <= n;i ++) add(0,i,0);
	for(int i = 1;i < n;i ++) add(i + 1,i,0);
	int tmp = spfa(0);
	if(tmp <= -1)
		printf("%lld\n",tmp);
	else
		printf("%lld\n",spfa(1));
	return 0;
}

习题

P1993 小 K 的农场

P4926 [1007] 倍杀测量者 利用对数的性质转化成差分约束系统

P2474 [SCOI2008] 天平

P3530 [POI2012] FES-Festival Tarjan 结合差分约束

[ABC087D] People on a Line