差分约束系统和2-SAT

Nannan Lv5
  2023-07-31 17:16 2023-07-31 17:16 Created   2024-09-30 19:43:35 2024-09-30 19:43:35 Updated      

差分约束系统和

介两类题都是偏建模的题，什么意思嘞，人话就是原本不是图论的题我们通过建模转化为图论的题。

其中差分约束背后的逻辑的最短路，是。

一、差分约束系统

1.1 差分约束介绍和求解

1.1.1 介绍

差分约束系统是下面 这种形式的多元一次不等式组(为已知量）：

（每个不等式称为一个约束条件，都是两个未知量之差小于或等于某个常数）

1.1.2 求解

在算法竞赛中，很多题目会给出（或隐性地给出）一系列的不等关系，我们可以尝试把它们转化为差分约束系统来解决。

我们设 ，移项得。

(特别的：如果是我们可以转化成：

正常来说，在我们没有任何前置条件的情况下我们怎么解这样一组方程？

比如：

我们先改写方程为：

我们设的初值为，然后不断调整，直到所有变量都满足条件。

调整方法：

所有限制，如果发现，那么取。

存在的问题？

  1. 正确性
  2. 时间复杂度

观察这个不等式和我们求最短路问题中的三角形不等式,的相似之处。

（流程：

1
2
3
4
dist[s] = 0;//初始起点
初始标号设为∞
for(每条边v->u , w)
	dist[u] = min(dist[u],dist[v]+w);

)

时间复杂度——>迭代轮不终止的话就是存在负环。

那么通过我们解决了正确性和时间复杂度的问题。

如果迭代轮数超过轮，那就是无解，时间复杂度。

利用这一点，我们可以把它转化为一个图论问题。也就是说，对于每一个 ，我们都从 到建一条边，边权为 。

这样建出的有向图，它的每个顶点都对应差分约束系统中的一个未知量，源点到每个顶点的最短路对应这些未知量的值，而每条边对应一个约束条件。

那么对于限制，我们从连一条边，求最短路，那么就是合法解。

1.2最大或最小的解

我们解决了有无解的问题，接下来考虑第二个问题：非负解，并且每个变量尽量小。

这相当于我们又引入了关于单个变量的额外限制。

首先我们知道，对于一组合法解，那么也是合法解。

1.解决非负

方法：引入辅助变量。

我们把当成基准，最后整体减去一个值，使得。

我们要，那么即

注意，这相当于了添加了以下约束条件：

2.解决每个变量尽量小

实际上我们按解出来的是一组最大解。

最大解：每个变量都取到最大值。

为什么呢，明明我们求的是最短路，我们得到的是最大值？

解释：

![image-20230729204813006](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230729204813006.png)

![image-20230729204708767](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230729204708767.png)

所以，其实我们得到的是满足条件的最大值。

那么如何求最小值呢？

最大值=-最小值

那么我们对于

改写为:$-x’{u}-(-x’{v})\leq w即x’{v}-x’{u}\leq w$

那么我们在反图里面求最大值，反过来就可以得到原图最小值。

1.3 建模

对应到图论里面是什么样子呢？

还是上述例子：

![image-20230729194939124](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230729194939124.png)

实际上取哪个点为源点是无关紧要的，但是，有时候我们得到的图不是连通的，这样求出来的结果很容易出现INF。为了避免这种情形，我们习惯人为地增加一个超级源点。

例如我们现在人为地新增一个0号点（或n+1号点），从它向所有顶点连一条边权为0的边：

![image-20230729195019373](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230729195019373.png)

现在我们以0号点为源点求各点的最短路即可。

由于我们要求的是非负解，我们可以把设为另一个数而不是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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010;
int n,m,x[N];
vector<array<int,3>>e;
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		//e.push_back({u,v,w});
		e.push_back({v,u,w});//记反图
	}
	for(int i = 1;i<=n;i++)
	{
		e.push_back({i,0,0});
	}
	for(int i = 1;i<=n;i++)
		x[i] = 1<<30;
	for(int i = 1;i<=n;i++)
	{
		for(auto [u,v,w]:e)
		{
			x[u] = min(x[u],x[v]+w);
		}
	}
	for(auto [u,v,w]:e)
	{
		if(x[u]>x[v] + w)
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	for(int i = 1;i<=n;i++)
		cout<<x[0]-x[i]<<" ";
	cout<<endl;
}

还有一种写法，它不用把图反过来。而是我们换一种迭代方法。介个的原理和我们边反向是一样的。

对于

我们之前写的是

我们也可以写成: 然后迭代方式改为：

注意一开始初始化为

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010;
int n,m,x[N];
vector<array<int,3>>e;
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e.push_back({u,v,w});
	}
	for(int i = 1;i<=n;i++)
	{
		e.push_back({0,i,0});
	}
	for(int i = 1;i<=n;i++)
		x[i] = -(1<<30);
	for(int i = 1;i<=n;i++)
	{
		for(auto [u,v,w]:e)
		{
			x[v] = max(x[v],x[u]-w);
		}
	}
	for(auto [u,v,w]:e)
	{
		if(x[u]>x[v] + w)
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	for(int i = 1;i<=n;i++)
		cout<<x[i]-x[0]<<" ";
	cout<<endl;
}

1.4例题

例题1：SCOI2011, 糖果

思路：因为要求最小的解，需要建反图。

根据差分约束建图：

  1. 等于的情况：

    转化为且

  2. 小于的情况:

    因为我们没有办法做小于的情况，那么我们把转化为

  3. 小于等于的情况：

    转化为

然后号点向每个点连一条边权为的边。

考虑解的情况：

由于我们的边只有等于的边和等于的边。

  1. 有解：每个里面边权都是。
  2. 无解：和在一个里面且连了一条-1的边，说明有负环，那无解。

所以我们先缩点变成一个,这个时候我们最短路可以用拓扑序或记忆化搜索求了。

时间复杂度。

例题2：POI2012, Festival

思路：

根据条件转化：

  2. 即

转化到图上就是连了一条的边，连了一条的边，连了一条的边。

看有没有解就是解这个差分约束，看有没有负环。

但是对于某些点之间只有小于关系或者没有关系(只有单边或没有边)，那么可以使得这些点权值都不同(因为我们希望不同种的成绩尽量多)。而有些点对之间他们既有大于关系又有小于关系，所以差是被限制的。

我们发现：

  1. 强连通分量之间值域可以实现不交,答案是每部分相加

  2. 边权只有，和那么我们的每个取值是连续的。严格来说，因为边权绝对值不超过，如果合法解一部分小于,一部分大于,那么小于的部分到大于的部分只有小于关系，不是强连通的，矛盾。

    不严格来说，可以理解成最短路一定是上一个点连过来的，所以距离标号只会差，没有道理说之间有某个点标号不存在。

    即对于每个，我们希望尽量大。

    我们可以枚举是哪一个。根据最短路求到的是每个的。

    如果我们对每个点求最短路复杂度肯定是不对的。我们可以用求多源最短路。

我们可以考虑对每个分开做，最后把答案加起来就行了。

总结：第一步连边，第二步求最短路，第三步每个求最大的

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
73
74
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =610;
const int inf = 1<<29;
int n,m1,m2;
int g[N][N],ans;
bool vis[N];
int main()
{
	cin>>n>>m1>>m2;
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
			g[i][j] = (i==j)?0:inf;
	for(int i = 1;i<=m1;i++)
	{
		int a,b;
		cin>>a>>b;
		/*
			x[a] - x[b]<= -1
			x[b] - x[a] <= 1
		*/
		//注意要取min，因为如果我们之前已经有一条为0的边，那就不对了
		g[b][a] = min(g[b][a],-1);
		g[a][b] = min(g[a][b],1);
	}

	for(int i = 1;i<=m2;i++)
	{
		int a,b;
		cin>>a>>b;
		g[b][a] = min(g[b][a],0);
	}

	for(int k = 1;k<=n;k++)
	{
		for(int i = 1;i<=n;i++)
		{
			for(int j = 1;j<=n;j++)
			{
				g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
			}
		}
	}
	for(int i = 1;i<=n;i++)
	{
		if(g[i][i]<0)
		{
			cout<<"NIE\n";
			return 0;
		}
	}
	for(int i = 1;i<=n;i++)
	{
		if(!vis[i])
		{
			vector<int>v;
			for(int j = 1;j<=n;j++)
			{
				if(g[i][j]<=n && g[j][i]<=n)//判成<inf可能有问题
				{
					v.push_back(j);
					vis[j] = true;
				}
			}
			int d = 0;
			for(auto p:v)
				for(auto q:v)
					d = max(d,g[p][q]);
			ans += d+1;
		}
	}
	cout<<ans<<endl;
}

二、

2.1 的介绍和求解

2.1.1介绍

定义：，简单的说就是给出个集合，每个集合有两个元素，已知若干个 ，表示 与矛盾（其中与属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。

用人话说就是：给你个变量,每个变量只能取值。同时给出形如 ,其中表示其中一个。求解就是求满足限制的一组合法解。

比如：

Misplaced &x_1 & x_2= 0可以表示为：或至少一个成立。

可以表示为：至少一个成立，至少一个成立。

可以表示为：至少一个成立。

2.1.2 求解

我们首先把每个变量拆点：

比如：和至少一个成立。

如果(其中一个不成立要推出另一个成立)，那么我们可以从向连边，同理。

再比如说：。

我们可以由一个命题推出另一个命题。

什么时候发现矛盾呢？

以下表示,表示。

当能推出,能推出，即能互相推出，说明矛盾。

我们把逻辑关系画成图的话，我们发现和在同一个强连通分量里面，就矛盾。如果对于所有的，我们的与都不在同一强连通分量里面就不矛盾。

那么我们的做法是什么呢？

我们先求一下强连通分量，如果和在同一个强连通分量里面，肯定矛盾。然后我们对比一下和(在缩点完得到的上的)拓扑序，考虑把拓扑序靠后的一个点设为真。因为如果它们之间单连通则一定是拓扑序较小的点可达拓扑序较大的点，当然如果它们之间不连通怎样赋值都可以。

我们在求的时候我们知道，先出栈的拓扑序更靠后。那么我们做完之后求出了每个强连通分量的标号，那么标号(反序的拓扑序)越前的，拓扑序越靠后。那么换句话说就是我们看两个标号，哪个更靠前就可以了。

2.2 模板题

例题1：JSOI2010, 满汉全席 

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
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<int>edge[N];
int n,m;
int dfn[N],low[N],ins[N],idx,bel[N],cnt;
stack<int>stk;
void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);
	for(auto v:edge[u])
	{
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u] == low[u]){
		++cnt;
		while(1)
		{
			int v = stk.top();
			ins[v] = false;
			bel[v] = cnt;
			stk.pop();
			if(u==v)break;
		}
	}

}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		//标号0...2n-1 对于满式mi:2*i,hi:2*i+1
		for(int i = 0;i<2*n;i++)
			dfn[i] = 0,edge[i].clear();
		idx = cnt = 0;
		for(int i = 1;i<=m;i++)
		{
			char ty1,ty2;
			int u,v;
			cin>>ty1>>u>>ty2>>v;
			--u,--v;
			u = u*2+(ty1=='h');
			v = v*2+(ty2=='h');
			edge[u^1].push_back(v);
			edge[v^1].push_back(u);
		}

		for(int i = 0;i<2*n;i++)
		{
			if(!dfn[i])
				dfs(i);
		}
		bool ok = true;
		for(int i = 0;i<n;i++)
		{
			//bel[2*i]<bel[2*i+1]选2*i
			if(bel[2*i]==bel[2*i+1])
			{
				ok = false;
				break;
			}
		}
		if(ok)
			cout<<"GOOD\n";
		else
			cout<<"BAD\n";
	}
	
}

例题2：USACO2011 Jan, 奶牛议会

思路：

考虑：恒为真，假？

我们强行设是假的，如果这个时候是无解，那么就一定要是真的。

那么怎么强行设是假的呢？方法：把向连边。给这个东西重新跑一遍2-SAT(O(n+m)),如果是无解的那我们一定是真的。

在原图的基础上跑，如果推出那么是假的是真的，否则如果反过来推出，那么恒为真的。

如果和是没有可达关系的，这种情况一定是问号。

我们缩完点之后是一个，如果加一条边，它们还是不能成环，说明无可达关系。也就是说不会变，那么原来有解现在还是有解的。

那么我们可以先对这些点对判可达关系，然后再去判恒为真还是恒为假的。

注意：每个点会建出2个点，我们数组要开2倍。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5010;
vector<int>edge[N];
int n,m;
int dfn[N],low[N],ins[N],idx,bel[N],cnt;
stack<int>stk;
int vis[N];
char ans[N];
void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);
	for(auto v:edge[u])
	{
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u] == low[u]){
		++cnt;
		while(1)
		{
			int v = stk.top();
			ins[v] = false;
			bel[v] = cnt;
			stk.pop();
			if(u==v)break;
		}
	}

}

void dfs2(int u)
{
	vis[u] = 1;
	for(auto v:edge[u])
		if(!vis[v])
			dfs2(v);
}

bool check(int s,int t)
{
	memset(vis,0,sizeof(vis));
	dfs2(s);
	return vis[t];
}



int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		char ty1,ty2;
		int u,v;
		cin>>u>>ty1>>v>>ty2;
		--u,--v;
		u = u*2+(ty1=='Y');
		v = v*2+(ty2=='Y');
		edge[u^1].push_back(v);
		edge[v^1].push_back(u);
	}

	for(int i = 0;i<2*n;i++)
		if(!dfn[i])
			dfs(i);

	bool ok = true;
	for(int i = 0;i<n;i++)
	{
		//bel[2*i]<bel[2*i+1]选2*i
		if(bel[2*i]==bel[2*i+1])
		{
			ok = false;
			break;
		}
	}
	if(!ok)
		cout<<"IMPOSSIBLE\n";
	else
	{
		for(int i = 0;i<n;i++)
		{
			if(check(2*i,2*i+1))ans[i] = 'Y';
			else if(check(2*i+1,2*i))ans[i] = 'N';
			else ans[i] = '?';
		}
		cout<<ans<<endl;
	}
}

2.3 不那么模板的题

例题3：NOI2017, 游戏

因为地图有3个限制，那我们如果枚举,那每个地图枚举一次，那有个地图，时间复杂度就是。那么我们考虑另一种枚举方法：,这样我们枚举完种就能覆盖所有情况了，那枚举的时间复杂度就是，再去跑2-SAT，时间复杂度就是。

更进一步优化，我们每次随机,我们每次有的概率能随机中，那么个都是对的的概率就是,期望次数,时间复杂度。

  • Title: 差分约束系统和2-SAT
  • Author: Nannan
  • Created at : 2023-07-31 17:16:00
  • Updated at : 2024-09-30 19:43:35
  • Link: https://redefine.ohevan.com/2023/07/31/六、差分约束系统和2-SAT/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
差分约束系统和2-SAT
  1. 差分约束系统和
    1. 一、差分约束系统
      1. 1.1 差分约束介绍和求解
        1. 1.1.1 介绍
        2. 1.1.2 求解
      2. 1.2最大或最小的解
      3. 1.3 建模
      5. 1.4例题
        1. 例题1：SCOI2011, 糖果
        2. 例题2：POI2012, Festival
    2. 二、
      1. 2.1 的介绍和求解
        1. 2.1.1介绍
        2. 2.1.2 求解
      2. 2.2 模板题
        1. 例题1：JSOI2010, 满汉全席
        2. 例题2：USACO2011 Jan, 奶牛议会
      3. 2.3 不那么模板的题