2-SAT 学习笔记

本文同载于本人的洛谷文章。

参考资料

算法

2-SAT 用于解决什么样的问题？

问题

给定 \(n\) 个大小为 2 的集合，每个集合要选其中一个元素，不能同时选，有 \(m\) 个条件 \((a,b)\) 代表元素 \(a,b\) 不能同时选，构造方案或判定无解。

例子

有 3 个集合：\(\{a,\neg a\},\{b,\neg b\},\{c,\neg c\}\)，条件 \((a,\neg b),(\neg b ,\neg c)\)。

解法

因为集合内不能同时选，所以集合内的两个元素我们互相取反。

把每个元素当成一个点，即把 \(\{a,\neg a\}\) 分成两个点。

现在我们连有向边，每条边 \(a\) 连向 \(b\) 代表当 \(a\) 选时 \(b\) 也一定选。

因为每个集合选一个元素，即不能同时选择。

所以对于条件 \((a,b)\)，若 \(a\) 为真，则 \(\neg b\) 为真，反之同理。

于是我们连好边了，然后求用 \(Tarjan\) 强连通分量。

此时若 \(\neg a\) 和 \(a\) 在同一个强连通分量内，则无解。

然后构造解，考虑按照拓扑序。

例如有 \(a\rightarrow b \rightarrow \neg a\)，则我们应该选 \(\neg a\) 而不应该选 \(a\)。

所以我们要按照拓扑序从大到小选择，但我们不用真的拓扑排序，我们求强连通分量时缩点的编号就是反着的拓扑序。

于是对于 \(\{a,\neg a\}\) 我们把拓扑序大的选择（缩点后编号小的选择）。

有 \(O(m)\) 条边，\(O(n)\) 个点，跑 \(Tarjan\) 是 \(O(n+m)\) 的。

模板题

P4782 2-SAT 模板

注意这道题是"\(x_i\) 为 \(a\) 或 \(x_j\) 为 \(b\)"，即两个至少有一个满足条件，即 \(x_i=\neg a\) 和 \(x_j=\neg b\) 不能同时存在，于是就转化成了上面所说的条件了。

其实就是 \(a \lor b=\neg ((\neg a)\land (\neg b))\)

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=2e6+5;
int stk[N],bz[N],dfn[N],low[N],num,dfn1,top;
vector<int> g[N];
int neg(int x){
	if(x<=n)return x+n;
	return x-n;
}
int nm[N];
void dfs(int x){
	dfn[x]=low[x]=++dfn1,bz[x]=1,stk[++top]=x;
	for(int v:g[x]){
		if(!dfn[v]) dfs(v),low[x]=min(low[v],low[x]);
		else if(bz[v]) low[x]=min(dfn[v],low[x]);
	}
	if(dfn[x]==low[x]){
		++num;
		while(stk[top]!=x)nm[stk[top]]=num,bz[stk[top]]=0,top--;
		nm[x]=num,bz[x]=0,top--;
	}
}
int ans[N];
int main(){
//	freopen("2-sat.in","r",stdin);
//	freopen("2-sat.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int _i=1;_i<=m;_i++){
		int i,a,j,b;
		cin>>i>>a>>j>>b;
		a^=1,b^=1;
		if(!a)i=neg(i);
		if(!b)j=neg(j);
		g[i].push_back(neg(j));
		g[j].push_back(neg(i));
	}
	for(int i=1;i<=2*n;i++){
		if(!dfn[i])dfs(i);	
	}
	for(int i=1;i<=n;i++){
		if(nm[i]==nm[neg(i)]){
			cout<<"IMPOSSIBLE";
			return 0;
		}
		if(nm[i]<nm[neg(i)])ans[i]=1;
	}
	cout<<"POSSIBLE\n";
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
}

本质思想

其实就是每个位置二选一，同时连边表示选了一个另一个必须选。

最后跑强连通分量求拓扑序，同时判断是否无解。

用这个思路可以应用在很多题目上。

注意：连边关系一定要列全，否则最后的答案可能不满足约束条件。

习题

jzoj 8097

P3209 [HNOI2010] 平面图判定

因为给出的环包括了 \(n\) 个点，所以我们只用考虑除了环以外的边。

对于一条边，它可以在环内或环外，而它又不能与其他边相交。

这就是每个点选 0 或 1，同时有些边不能同时选 0 或 1，这可以用 2-SAT 来做。

我们重新标号，则对于 \(a<x<b<y\) 的边 \((a,b),(x,y)\) 不能选在同一边。

乍一看这个东西几乎不可做，直接做是 \(O(m^2)\) 的，过不了。

但是平面图有性质，即 \(m\le 3*n-6\)，\(m\) 为边数，\(n\) 为点数。

于是对于不满足性质的直接判掉，此时 \(m\) 与 \(n\) 同阶，连边时间复杂度为 \(O(n^2)\)。

每条边分成两个点跑 2-SAT，由于 \(m\) 与 \(n\) 同阶，所以复杂度为 \(O(n)\)。

总时间 \(O(T(n^2+m))\)。

P3825 [NOI2017] 游戏

算法 1

如果 \(x\) 的个数为 0，则每个位置都是二选一，再带上一些限制，这是 2-SAT 板子题。

建边方式：

设题目所给条件为若 \(u\) 选了，则 \(v\) 必须选。

先看若 \(u\) 存在而 \(v\) 不存在，则 \(u\) 不能选，于是连边 \(u\rightarrow u'\)，就能使只能选 \(u'\)。

若 \(u\) 和 \(v\) 都存在：

• 先连边 \(u\rightarrow v\)，即 \(u\) 选了后 \(v\) 必须选。

• 再连边 \(v'\rightarrow u'\)，即选 \(v'\)，则不选 \(v\)，则 \(u\) 不能选，则选 \(u'\)。

判断有无解和构造方案与 2-SAT 板子一样。

期望得分 45 pts。

算法 2

我们可以 \(O(3^d)\) 枚举每个 \(x\) 的位置是选 \({A,B,C}\) 中的一种，对于剩下的部分做算法 1。

时间复杂度 \(O(3^d(n+m))\)。

期望得分 80 pts。

算法 3

考虑直接转化为对所有点的 2-SAT。

我们可以 \(O(3^d)\) 枚举每个 \(x\) 是 \(\{A,B\},\{A,C\},\{B,C\}\) 中的一种二选一，之后就如算法 1。

时间复杂度 \(O(3^d(n+m))\)，不能通过。

期望得分 80 pts。

算法 4

考虑改进算法 3。

对于每个 \(x\)，只需枚举 \(\{A,B\},\{B,C\}\) 就可以覆盖 \(x\) 的所有可选的方案了。

也就是每个 \(x\) 只用枚举两种二选一。

时间复杂度 \(O(2^d(n+m))\)。

期望得分 100 pts。