mydcwfy's Blog

差分约束

Posted on
Symbols count in article: 5.5k Reading time ≈ 12 mins.

比较重要的知识点。

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

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

1. 定义与应用场景

形如

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

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

2. 应用 1

建图方式

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

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

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

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

真的可以吗

其实是不完全可以的。

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

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

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

步骤

  1. 先将每一个不等式 $x(i)\leq x(j) +c(j,i)$ 转换成从 $j$ 到 $i$ 连一条 $c(j,i)$ 的边。

  2. 找一个源点，使它能到每一条边。

  3. 从这个点找单源最短路。

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

易得，从一个环到自己且是负的话，就是 $x_i\leq x_j+c(j,i)\leq x_k+c(k,j)+c(j,i)\leq…\leq x_i+c(j,i)+c(k,j)+… $

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

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

如果有解，这一组解就是 $x(i)=dis(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]糖果

  1. $A=B \Leftrightarrow A\geq B,B\geq A$

  2. $A<B \Leftrightarrow B\geq A+1$

  3. $A\leq B \Leftrightarrow B\geq A$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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.区间

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

利用前缀和的思想：

  1. $S(0)=0$

  2. $S(i)$ 表示$1$ 到 $i$ 中，选出数的个数。

  3. $0\leq S(i)-S(i-1) \leq 1 \Leftrightarrow S(i)\geq S(i-1),S(i-1)\geq S(i)-1$

  4. $S(b)-S(a-1)\geq c$

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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. 雇佣收银员

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

  1. $0\leq x(i) \leq num(i)$
  2. $x(i-7)+x(i-6)+…+x(i-1)+x(i)\geq r(i)$

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

  1. $0 \leq s(i)-s(i-1)\leq num(i)$

  2. $i\geq 8 \Leftrightarrow s(i)-s(i-8)\geq r(i)$

  3. $0\leq i \leq 7\Leftrightarrow s(i)+s(24)-s(i+16)\geq r(i)$

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

消哪个呢？

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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;
}