差分约束 | mydcwfy's Blog

比较重要的知识点。

应用1：求不等式的可行解

应用2：求最大值或最小值

1. 定义与应用场景

形如

x (i) \leq x (j) + c (i, j)

的形式的不等式组，即可用差分约束。

这类题目大概要求我们要 数形结合，可能是最好的解释了。

2. 应用 1

建图方式

由于最短路一定是最短路~~（废话~~，那么每一条边的转移一定是有效的，如果出现了 $d i s (i) > d i s (j) + w (j, i)$ ，那么 $d i s (i)$ 就不是最短路了。

所以我们可以得到最短路的三角形不等式： $d i s (i) \leq d i s (j) + w (j, i)$

对于 $x (i) \leq x (j) + c (j, i)$ ，我们可以从 $j$ 到 $i$ 连一条 $c (j, i)$ 的边。

但是这里没有源点，我们可以随意找一个点。

~~真的可以吗~~

其实是不完全可以的。

如果从源点到不了所有的边，那么这个点不可行。

注意，不是遍历到所有的点，因为可能有孤立的点，与主体无关。

好像一般是不会出现不联通的边吧……

步骤

先将每一个不等式 $x (i) \leq x (j) + c (j, i)$ 转换成从 $j$ 到 $i$ 连一条 $c (j, i)$ 的边。
找一个源点，使它能到每一条边。
从这个点找单源最短路。

有一个问题：有负环是什么情况？

易得，从一个环到自己且是负的话，就是 $x_{i} \leq x_{j} + c (j, i) \leq x_{k} + c (k, j) + c (j, i) \leq \dots \leq x_{i} + c (j, i) + c (k, j) + \dots$

又 $c (j, i) + c (k, j) + \dots < 0$ ，所以就是 $x_{i} \leq x_{i} + k$ ，其中 $k < 0$ ，显然是不可能的。

同样，如果原不等式组无解，那么图有负环。（否则一定能构造出一组解）

如果有解，这一组解就是 $x (i) = d i s (i)$ 。当然，可以加同样的值，原不等式依然成立。

另外，我们也可用最长路。

改为 $x (j) \geq x (i) - c (i, j)$ 的方式，并将从 $i$ 到 $j$ 连一条 $- c (i, j)$ 的边。

我们就反过来了，如果有正环，那么无解了。

3.应用2

结论：如果是最小值，那么求最长路；如果是最大值，那么求最短路。

首先，通过前面的转化，我们发现，对于同一个题，我们既可以构造最长路，也可以构造最短路。

虽然有些反直觉，为什么是正确的呢？

假设我们讨论最长路。

因为最长路，有一个式子 $x (i) \geq x (j) + w (j, i)$ ，那么一定会有一个 $j$ ，满足 $x (i) = x (j) + w (j, i)$ （否则 $x (i)$ 从何处来？），那么就不会存在小于 $x (i)$ 的解，因为 $x (i) \geq x (j) + w (i, j)$ ，所以 $x (i)$ 就是所有解答最小值。

问题1：如何转化 $x (i) \leq c (i)$ ？

建立一个超级源点 $x (0)$ ，从 $0$ 到 $i$ 的建立 $c (i)$ 的边。

以 $x (i)$ 的最大值为例，从 $x (i)$ 出发的不等式链，可以转化为一个只含变量 $x (0)$ 的值。

所有上界的最小值，即为 $x (i)$ 的最大值。

我们又可以发现一个有趣的性质：

每一个不等式链，都是 $0$ 到 $i$ 的一条路径。

然后，这些上界的最小值，其实就是最短路！

反过来，求最小值的话，应该求最长路。

这个就不再赘述。

4.例题

T1:

Luogu P3275 [SCOI2011]糖果

$A = B \Leftrightarrow A \geq B, B \geq A$
$A < B \Leftrightarrow B \geq A + 1$
$A \leq B \Leftrightarrow B \geq A$

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;

const int N=2e5+10,INF=1e9,M=3e5+10;
int d[N],h[N],e[M],ne[M],w[M],cnt[N],n,m,S,idx;
bool vis[N];

void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

bool SPFA()
{
	memset(d,0xcf,sizeof d);
	stack <int> q;
	q.push(S);d[S]=0;cnt[S]=0;
	while (!q.empty())
	{
		int x=q.top();q.pop();
		vis[x]=0;
		for (int i=h[x];~i;i=ne[i])
			if (d[e[i]]<d[x]+w[i])
			{
				d[e[i]]=d[x]+w[i];
				cnt[e[i]]=cnt[x]+1;
				if (cnt[e[i]]>n) return false;
				if (!vis[e[i]]) vis[e[i]]=1,q.push(e[i]);
			}
	}
	return true;
}

int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	int a,b,op;
	while (m--)
	{
		scanf("%d",&op);scanf("%d %d",&a,&b);
		switch(op)
		{
			case 1:add(b,a,0),add(a,b,0);break;
			case 2:add(a,b,1);break;
			case 3:add(b,a,0);break;
			case 4:add(b,a,1);break;
			case 5:add(a,b,0);break;
		}
	}
	S=0;
	for (int i=1;i<=n;++i) add(0,i,1);
	if (!SPFA()) return puts("-1"),0;
	else
	{
		long long ans=0;
		for (int i=1;i<=n;++i) ans+=(long long)d[i];
		cout<<ans<<endl;
	}
	return 0;
}

T2:

AcWing 362.区间

差分约束最难的地方就在于找不等关系。

利用前缀和的思想：

$S (0) = 0$
$S (i)$ 表示 $1$ 到 $i$ 中，选出数的个数。
$0 \leq S (i) - S (i - 1) \leq 1 \Leftrightarrow S (i) \geq S (i - 1), S (i - 1) \geq S (i) - 1$
$S (b) - S (a - 1) \geq c$

可以发现， $0$ 可以遍历到所有点，也可以遍历到所有边。

那么这样就可以完成对每个点的遍历了。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;

const int N=50010,M=150050;
int h[N],e[M],ne[M],idx,w[M];
int n,d[N];
bool vis[N];

void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void SPFA()
{
	memset(d,0xcf,sizeof d);
	stack <int> q;
	q.push(0);d[0]=0;
	while (!q.empty())
	{
		int x=q.top();q.pop();
		vis[x]=0;
		for (int i=h[x];~i;i=ne[i])
			if (d[e[i]]<d[x]+w[i])
			{
				d[e[i]]=d[x]+w[i];
				if (!vis[e[i]]) vis[e[i]]=1,q.push(e[i]);
			}
	}
	return;
}

int main()
{
	cin>>n;
	memset(h,-1,sizeof h);
	int a,b,c,ans=0;
	for (int i=1;i<=n;++i)
	{
		scanf("%d %d %d",&a,&b,&c);
		a++;b++;ans=max(ans,b);
		add(a-1,b,c);
	}
	for (int i=1;i<=ans;++i) add(i-1,i,0),add(i,i-1,-1);
	SPFA();
	cout<<d[ans]<<endl;
	return 0;
}

T3:

AcWing 393. 雇佣收银员

特别拿出来讲的目的是其实现较难。

$0 \leq x (i) \leq n u m (i)$
$x (i - 7) + x (i - 6) + \dots + x (i - 1) + x (i) \geq r (i)$

不满足形式，用前缀和优化：

$0 \leq s (i) - s (i - 1) \leq n u m (i)$
$i \geq 8 \Leftrightarrow s (i) - s (i - 8) \geq r (i)$
$0 \leq i \leq 7 \Leftrightarrow s (i) + s (24) - s (i + 16) \geq r (i)$

最后一项有 $3$ 个变量，所以要消元（~~回到了数学课~~）。

消哪个呢？

看到 $s (24)$ 比较好欺负，又看到时间是允许我们枚举的。

那么枚举 $s (24)$ 的取值，然后分别跑。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;

const int N=1e5+10,M=3e5+10,INF=1e9;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cnt[N],num[26],r[26],n,st[N];
bool vis[N];

void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void build(int s24)
{
	memset(h,-1,sizeof h);idx=0;
	for (int i=1;i<=24;++i) add(i-1,i,0),add(i,i-1,-num[i]);
	for (int i=1;i<=7;++i) add(i+16,i,-s24+r[i]);
	for (int i=8;i<=24;++i) add(i-8,i,r[i]);
	add(0,24,s24);add(24,0,-s24);
}

bool SPFA(int s24)
{
	build(s24);
	memset(cnt,0,sizeof cnt);
	memset(d,0xcf,sizeof d);
	for (int i=0;i<N;++i) vis[i]=0;
	d[0]=0;
	queue <int> q;q.push(0);
	while (!q.empty())
	{
		int x=q.front();q.pop();
		vis[x]=0;
		for (int i=h[x];~i;i=ne[i])
			if (d[e[i]]<d[x]+w[i])
			{
				d[e[i]]=d[x]+w[i];
				cnt[e[i]]=cnt[x]+1;
				if (cnt[e[i]]>=25) return false;
				if (!vis[e[i]]) vis[e[i]]=1,q.push(e[i]);
			}
	}
	return true;
}

int main()
{
	int t;cin>>t;
	while (t--)
	{
		for (int i=1;i<=24;++i) scanf("%d",r+i);
		cin>>n;
		for (int i=1;i<=n;++i) scanf("%d",st+i);
		for (int i=1;i<=n;++i) num[st[i]+1]++;
		bool flag=1;
		for (int i=1;i<=n;++i)
			if (SPFA(i))
			{
				cout<<i<<endl;
				flag=0;
				break;
			}
		if (flag) puts("-1");
	}
	return 0;
}