差分约束系统的应用

如果告诉你在一个三角形中，$B-A \leqslant c, C-B \leqslant a, C-A \leqslant b$，怎么求 $C-A$ 的最大值呢？通过yy观察可以发现，$C-A$ 的最大值是 $min(a+c,b)$。这个答案如何得出？将这个三角形内的约束条件推广到更多约束条件呢？

差分约束系统（System of Difference Constraints），是求解关于一组变数的特殊不等式组之方法。

概念与定义

一个系统由 $n$ 个变量和 $m$ 个约束条件组成（就如同上面三角形里的例子），每个约束条件形如：$x_j-x_i \leqslant b_i$，那么这个系统就是一个差分约束系统（System of Difference Constraints）。这个定义很直观：用一系列不等式约束差分的域。

解法

仔细观察这个不等式：

可以发现它可以变形成：$x_j\leqslant x_i+b_i$。 是不是有点像 SPFA/Dijkstra 里修正最短路的判断方程（三角不等式）？！

所以我们就可以想到一个奇妙的做法：从 $i$ 到 $j$ 建边，边权为 $b_k$，最后增加一个源点 $s$，跑一遍最短路就可以了！对于大于等于的情况也是一样的。

在求解差分约束系统的时候一般我们用 SPFA（Bellman-ford）算法求最短路而不用 Dijkstra，因为 SPFA 可以判断负环，即无解情况。但是在题目告诉我们一定有解时还是尽量用 Dijkstra+Heap，不然容易被卡（在洛谷上看见一句话：不卡你是情分，卡你是本分……）。

回到前面说的一个三角形里的情况：$B-A \leqslant c, C-B \leqslant a, C-A \leqslant b$，则 $C-A$ 的最大值是 $min(a+c,b)$。画出来的图就是：

graph LR;
A((A)) --c--> B((B));
B((B)) --a--> C((C));
A --b--> C

（我不知道为什么 Mermaid 画的图这么丑……）

例题与题解

POJ 1201 Intervals

POJ 1201 Intervals

题目大意是给你 n 个闭区间，每个闭区间 $[L_i,R_i]$ 里要求至少选择 $c_i$ 个数字。问你一共最少选多少数字。

如果用 $sum(i)$ 表示小于等于 $i$ 的数字中一共选了多少（其实就是前缀和），那么很显然根据题目中所给信息可以列出：

很显然是差分约束。建边求最长路即可。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=50005,maxe=150005,INF=1e9;
int n,s,t,dst[maxn];
int tot=0,lnk[maxn],nxt[maxe],son[maxe],w[maxe];
bool vis[maxn];
queue<int> que;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline void Init(){
	tot=0;
	s=INF;t=-INF;
	memset(lnk,-1,sizeof(lnk));
	memset(nxt,-1,sizeof(nxt));
	memset(son,-1,sizeof(son));
	memset(w,0,sizeof(w));
	memset(vis,0,sizeof(vis));
	memset(dst,0x80,sizeof(dst));
}
inline void add(int x,int y,int z){
	tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
	s=min(s,min(x,y));t=max(t,max(x,y));
}
inline void SPFA(){
	que.push(s);vis[s]=true;dst[s]=0;
	while (!que.empty()){
		int x=que.front();que.pop();vis[x]=false;
		for (int i=lnk[x];i!=-1;i=nxt[i]) if (dst[x]+w[i]>dst[son[i]]){
			dst[son[i]]=dst[x]+w[i];
			if (!vis[son[i]]) vis[son[i]]=true,que.push(son[i]);
		}
	}
}
int main(){
	while (scanf("%d",&n)!=-1){
		Init();
		for (int i=0;i<n;i++){
			int a=read(),b=read(),c=read();
			add(a-1,b,c);
		}
		for (int i=s+1;i<=t;i++) add(i,i-1,-1),add(i-1,i,0);
		SPFA();
		printf("%d\n",dst[t]);
	}
	return 0;
}

POJ 3159 Candies

POJ 3159 Candies

题目大意：有 n 个孩子分糖果，第 $a_i$ 个孩子认为第 $b_i$ 个孩子不应该分到比他分到糖果数多 $c_i$ 的糖果。问你分到最多糖果的孩子与分到最少糖果的孩子的糖果数量之差最大是多少。

更裸的差分约束，按题目描述建边，也就是 $d(b_i)-d(a_i) \leqslant c_i$。求最短路即可。

注意这题必须写 Dijkstra+Heap，写 SPFA 会被卡（据说可以用栈优化？）。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=30005,maxe=150005;
int n,m,dst[maxn];
int tot=0,lnk[maxn],nxt[maxe],son[maxe],w[maxe];
bool vis[maxn];
struct HeapElementInfo{
	int dst,id;
    bool operator <(const HeapElementInfo bb)const{
        return dst>bb.dst;
    }
};
priority_queue<HeapElementInfo> heap;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline void add(int x,int y,int z){
	tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void init(){
	memset(dst,0x3f,sizeof(dst));
}
inline void Dijkstra(){
	dst[1]=0;vis[1]=true;
	for (int i=lnk[1];i;i=nxt[i]) heap.push((HeapElementInfo){w[i],son[i]}),dst[son[i]]=w[i];
	for (int t=1;t<n&&!heap.empty();t++){
		HeapElementInfo now;
		for (;;){
			if (heap.size()==0) {printf("ERROR!\n");return;}
			now.id=heap.top().id;now.dst=heap.top().dst;heap.pop();
			if (now.dst==dst[now.id]&&!vis[now.id]) break;
		}
		vis[now.id]=true;
		for (int i=lnk[now.id];i;i=nxt[i]) if (!vis[son[i]]&&dst[now.id]+w[i]<dst[son[i]]){
			dst[son[i]]=dst[now.id]+w[i];
			heap.push((HeapElementInfo){dst[son[i]],son[i]});
		}
	}
}
int main(){
	n=read();m=read();
	init();
	for (int i=0;i<m;i++){
		int x=read(),y=read(),z=read(); // dst[y]-dst[x]<=z ==> dst[y]<=dst[x]+z
		add(x,y,z);
	}
	Dijkstra();
	printf("%d\n",dst[n]);
	return 0;
}

参考

差分约束系统 - 维基百科，自由的百科全书