差分约束系统

如果一个不等式组由 $n$ 个变量和 $m$ 个约束条件组成，形成 $m$ 个形如 $x_j-x_i\leq k$ （ $i,j\in[1,n]$ 且 $k$ 为常数）的不等式，则称其为 差分约束系统。换句话说，解决差分约束问题就是求解一组变量的不等式组。

问题转化

对于 $x_j-x_i\le k$ ，我们会发现它类似最短路网络中的三角不等式 $d_v-d_u\le w_{<u,v>}$ ，那是否可以通过最短路的形式解决呢？显然是可以的。

我们首先把这个不等式化一下，成 $x_j\le x_i+k$ 。可以推出， $x_j$ 的最大值只可能是 $x_i+k$ ，最小不限。

那我们再次假设如果 $x_j$ 跟 $x_{i'}$ ， $x_{i''}$ ， $x_{i'''}$ 都有关，我们就可以得到三个不等式，即一个不等式组：

\begin{cases} x_j\le x_{i'}+b \\\ x_j\le x_{i''}+b \\\ x_j\le x_{i'''}+b \end{cases}

那么 $x_j$ 满足所有不等式下的最大值应该是：

\min\{x_{i'}+b,x_{i''}+b,x_{i'''}+b\}

因为要满足所有不等式，所以必须要取最小值来满足所有的不等式。不等式解集应该是范围更小的那一个。

注意，我们上面提到的 $i$ 都可以模拟成 $j$ 的前继。

那么我们可以再次简化模型。

假设有多个 $x_i$ 是 $x_j$ 的前继，那么我们就可以得到一个式子，满足原不等式组的求解：

x_j=\min\{x_i+b\}

这不就是最短路嘛！

此时，可将每个变量看成一个顶点，并设一个超级源点 $x_0$ ，它连向每个顶点（除了自身）且边权为 $0$ ，这时再对每一个不等式 $x_j-x_i\le k$ 连一条边权为 $k$ 的有向边 $<i,j>$ ，此时用 $x_j$ 表示超级源点到 $j$ 的最短路，用 $x_i$ 表示超级源点到 $i$ 的最短路，由于有边 $<i,j>$ 存在，从而有 $x_j\le x_i+k$ ，即为原不等式的变形。

在有解的情况下，跑一遍最短路，最短路的答案 $d_i$ 正是原不等式组的一个解 $x_i$ 。

使用“最长路”求解也是可以的。

连边方法

差分约束问题可以转化为最短路或最长路问题，所以两种转化也就形成了两种不同的连边方法。

连边后求最短路
将 $x_j-x_i\le k$ 变形为 $x_j\le x_i+k$ ，即从 $i$ 到 $j$ 连一条边权为 $k$ 的边。加入超级源点后求最短路，得到 $x_i\le 0$ 所有 $x$ 最大解。
连边后求最长路
将 $x_j-x_i\le k$ 变形为 $x_i\ge x_j-k$ ，即从 $i$ 到 $j$ 连一条边权为 $-k$ 的边。加入超级源点后求最长路，得到 $x_i\ge 0$ 所有 $x$ 最小解。

显而易见地，两种方法求出来的解大概率是不同的。

判断无解

若求最短路，图中存在负环，则该不等式组无解。

此时，即可放心大胆地 SPFA，只需在 SPFA 的同时用一个数组来记录每个顶点入队次数，如果一个顶点入队次数大于 $n$ ，说明该图存在负环。对于 DFS_SPFA，只需看当前顶点如果访问过，说明该图存在负环。

模板

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	struct edge
	{
		int nxt,end,len;
	}e[1000000+5];
	int n,m,cnt=0,head[100000+5],vis[100000+5],dis[100000+5],in[100000+5];
	long long ans=0;
	queue<int>q;
	void add(int a,int b,int len)
	{
		e[++cnt]=(edge){head[a],b,len};
		head[a]=cnt;
	}
	int dfs_spfa(int now)
	{
		vis[now]=1;
		for(int i=head[now];i;i=e[i].nxt)
		{
			int to=e[i].end;
			if(dis[to]<dis[now]+e[i].len)
			{
				dis[to]=dis[now]+e[i].len;
				if(vis[to]) return 1;
				if(dfs_spfa(to)) return 1;
			}
		}
		vis[now]=0;
		return 0;
	}
	void bfs_spfa(int x)
	{
		q.push(x);
		while(!q.empty())
		{
			int now=q.front();q.pop();
			vis[now]=0;
			for(int i=head[now];i;i=e[i].nxt) 
			{
				int to=e[i].end;
	          	if(dis[to]<dis[now]+e[i].len)
	          	{
	          		dis[to]=dis[now]+e[i].len;
					if(!vis[to])
						q.push(to),vis[to]=1;
				}
			}
		}
		return;
	}
	void yzmain()
	{
		int a,b,c;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++) 
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,-c);
		}
		for(int i=1;i<=n;i++)
			add(0,i,0);
		for(int i=1;i<=n;i++)
			if(dfs_spfa(i)) {printf("NO");return;}
		bfs_spfa(0);
		for(int i=1;i<=n;i++)
			printf("%d ",dis[i]);
   		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

例题

P6145 [USACO20FEB]Timeline G

https://www.luogu.com.cn/problem/P6145。

连边方式：

for i from 1 to n
    add < 0,i > = Si
for i from 1 to c
	add < ai,bi > = xi

之后求最长路。

P4878 [USACO05DEC]Layout G

https://www.luogu.com.cn/problem/P4878。

连边方式：

for i from 1 to ML
    add < Ai,Bi > = Di
for i from 1 to MD
    add < Bi,Ai > = -Di
for i from 1 to n
    add < 0,i > = 0
for i from 2 to n
	add < i,i-1 > = 0

之后求最短路。差分约束题还是有很多条件在里面的，仔细看题是正道。

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/b3f0a63025b7/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 最短路差分约束

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158