差分约束系统学习笔记

差分约束系统，其实是一个类似网络流的，求一类不等式方程组的解的算法。

基本形式

差分约束系统主要用求这样的不等式方程组的一个解：

$\begin{cases}x_{a_1}-x_{b_1}\le y_1\\x_{a_2}-x_{b_2}\le y_2\\x_{a_3}-x_{b_3}\le y_3\\\qquad\cdots\cdots\\x_{a_m}-x_{b_m}\le y_m\\\end{cases}$

其中 $1\le a_i,b_i\le n$。

我们先考虑其中的一条不等式 $x_{a_1}-x_{b_1}\le y_1$，很明显可以转化为 $x_{a_1}\le x_{b_1}+y_1$。

观察这个等式，很容易联想到最短路中，点 $u$ 和点 $v$ 中间如果有一条长度为 $w$ 的边，那么这两个点之间的最短路长度一定小于等于 $w$。所以，我们可以把这 $m$ 个方程转换为 $m$ 条边，建出一个有向图来。

建完图后，我们考虑加一个大源点 $0$，向每一个未知数连一条长度为 $0$ 的边。这样，以 $0$ 作为源点跑出来的最短路，就是整个方程组的解了。

不过注意到，如果有负环，那么最短路是跑不出来的，这意味着方程组无解。

模板题代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const long long S=10000005,MS=100005;

int n,m;
int esum,to[S],nxt[S],c[S],h[MS];
int dis[MS],vis[MS];
bool inq[MS];

inline void add(int x,int y,int w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline bool slove()
{
	dis[0]=0;
	for(int i=1;i<=n;i++)
	{
		dis[i]=1e9;
	}
	memset(vis,0,sizeof(vis));
	memset(inq,0,sizeof(inq));
	queue<int> q;
	q.push(0);
	inq[0]=true;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=false;
		vis[u]++;
		if(vis[u]>n)
		{
			return false;
		}
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i],w=c[i];
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!inq[v])
				{
					inq[v]=true;
					q.push(v);
				}
			}
		}
	}
	return true;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		add(y,x,w);
	}
	for(int i=1;i<=n;i++)
	{
		add(0,i,0);
	}
	bool can=slove();
	if(!can)
	{
		puts("NO");
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			printf("%d ",dis[i]);
		}
		printf("\n");
	}
	return 0;
}

一些变形

• 遇到 $x_{a_i}\ge x_{b_i}+y_i$，可以反过来连边，变成 $x_{b_i}\le x_{a_i}-y_i$，或者同时乘以 $-1$，将符号反过来

• 遇到 $x_{a_i}-x_{b_i}=y_i$，可以转化为两个不等式：$x_{a_i}\le x_{b_i}+y_i$ 和 $x_{a_i}\ge x_{b_i}+y_i$

• 遇到 $[s_i,t_i]$ 的和为 $v_i$ 这类问题时，可以用前缀和转换为 $sum_{t_i}-sum_{s_i-1}=v_i$

练习题目

• 自己选着做吧……