2-SAT 学习笔记
djwj233
2021-08-19 21:49:02
### 2-SAT 是什么
2-SAT 的全称是 2-Satisfiability Problem，中文直译为「2 - 可满足性问题」。
一般地，2-SAT 的解法用以解决如下问题：
> 已知 $n$ 个二元组和 $m$ 组二元关系 $(u_i,v_i)$。
>
> 现在要在每个二元组中选出**恰好一个**元素构成一个集合，使得所有的 $(u_i,v_i)$ **不同时在集合中出现**。
>
> 尝试构造一组合法选择。
2-SAT 可以被形式化地表述为一个更具普适性的问题：
> 有 $n$ 个变量 $x_{1\cdots n}$。其中，一个变量 $x_i$ 的可能取值有且仅有 $x_{i,0}$ 和 $x_{i,1}$ 两种。
>
> 有 $m$ 条约束条件，每条约束条件可被描述为：
>
> 若 $x_i$ 被赋值为 $x_{i,p}$，则 $x_j$ 必须被赋值为 $x_{j,q}$。
>
> 求判断合法的值是否存在，若存在则构造一组合法的值。
事实上，2-SAT 可以被推广为 **$k$ - SAT** 问题（$k\geq 2$）。在 $k$ - SAT中，每个变量的可能取值有 $k$ 种。
- 3-SAT 是 Karp 的 21 个 NPC 问题之一，一般可以用于对一个问题是 NP-Hard 的证明；
- 而对一般的 $k>2$，$k$ - SAT 都是一个 NPC 问题；
- SAT 问题是人类第一个已知的 NPC 问题。
### 2-SAT 求解的主过程
有些地方提到可以用 爆搜 + 剪枝 的方式解决，不过个人觉得挺扯淡的。
不过注意：如果题目要求解**字典序最小**则必须用 DFS。
一般做法是使用 Tarjan 缩点的方式。
模板：[P4782 【模板】2-SAT 问题](https://www.luogu.com.cn/problem/P4782)
我们考虑建一张含有 $2n$ 个点的图，每个点表示一种赋值。
对于每个条件 $i,a,j,b$：
- 从 $(i,\lnot a)$ 向 $(j,b)$ 连边；
- 从 $(j,\lnot b)$ 向 $(i,a)$ 连边。
其中，连一条边 $u\to v$ 的意义是**如果选了 $u$ 就必须选 $v$**。
然后跑一遍 Tarjan 求出所有的 SCC，并检查所有的点：
- 如果存在一个点 $x$ 使 $(x,0)$ 和 $(x,1)$ 在同一个 SCC 中则说明无解。
- 否则，**按在 Tarjan 中被求出的顺序**枚举所有的 SCC，若当前的 SCC 中**没有一个点的否定**被选择，则选择这个 SCC 中的所有点。
为什么要按这个顺序呢？实际上，Tarjan 中 SCC 被求出的顺序可以看作是一个拓扑序的倒序。
根据上面我们的建图，一个没有出边的点的否定一定有出边，而有了出边就会对别的点造成影响。
因此，我们应该尽可能地选择没有出边的点。依次类推可以归纳证明**选择一个拓扑序更大的点一定更优**。
检查部分的实现可以写得较为简单：
```c++
fo(i,1,n) if(col[i]==col[i+n]) {
puts("IMPOSSIBLE");
exit(0);
}
puts("POSSIBLE");
fo(i,1,n) printf("%d ",col[i]>col[i+n]);
puts("");
```
完整代码：
```c++
#include <bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define il inline
const int N=2000010,M=2000010;
int n,m;
int head[N],Next[M],ver[M],tot;
void add_edge(int x,int y) {
ver[++tot]=y;
Next[tot]=head[x], head[x]=tot;
}
int dfn[N],low[N],cnt;
int st[N],top; bool ins[N];
int col[N],cur;
void tarjan(int x)
{
dfn[x]=low[x]=++cnt;
st[++top]=x, ins[x]=true;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(!dfn[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if(ins[y])
low[x]=min(low[x],low[y]);
}
if(low[x]==dfn[x]) {
cur++;
while(st[top]!=x)
col[st[top]]=cur, ins[st[top]]=false, top--;
col[st[top]]=cur, ins[st[top]]=false, top--;
}
}
int main()
{
cin>>n>>m;
fo(i,1,m) {
int x,y,a,b; scanf("%d%d%d%d",&x,&a,&y,&b);
add_edge(x+(a^1)*n,y+b*n);
add_edge(y+(b^1)*n,x+a*n);
}
fo(i,1,2*n) if(!dfn[i]) tarjan(i);
fo(i,1,n) if(col[i]==col[i+n]) {
puts("IMPOSSIBLE");
exit(0);
}
puts("POSSIBLE");
fo(i,1,n) printf("%d ",col[i]>col[i+n]);
puts("");
return 0;
}
```
### 例题
- [2018-2019 ACM-ICPC Asia Seoul Regional](https://codeforces.com/gym/101987) K TV Show Time
> 简要题面：（摘自 OI-Wiki）
>
> 有 $k$ 盏灯，每盏灯是红色或者蓝色，但是初始的时候不知道灯的颜色。
>
> 有 $n$ 个人，每个人选择 $3$ 盏灯并猜灯的颜色，一个人猜对两盏灯或以上的颜色就可以获得奖品。
>
> 判断是否存在一个灯的着色方案使得每个人都能领奖，若有则输出一种灯的着色方案。
看到有多个变量，每个变量有 $2$ 种赋值，且赋值有约束时可以考虑 2-SAT。
为保证一个人领奖，我们需要在他猜错其中一盏灯时钦定他别的两盏灯必须猜对。
这样就可以 2-SAT 了。[Code](https://codeforces.com/gym/101987/submission/128734803)
- [P3825 [NOI2017] 游戏](https://www.luogu.com.cn/problem/P3825)
我们注意到大多数的地图都只能使用 $2$ 种赛车，这启发我们使用 2-SAT。
但是还有 $d$ 幅所有赛车都能使用的地图，如果暴力枚举这 $d$ 幅地图的状态，复杂度将会达到 $\Theta(3^d(n+m))$，无法通过。
怎么优化呢？实际上我们对每幅 $x$ 地图只需枚举它是 $a$ 型或者 $b$ 型就可以了，这两种涵盖了所有三种赛车。
复杂度 $\Theta(2^d(n+m))$，可以通过，不过细节有点多。[Code](https://www.luogu.com.cn/record/58018165)
核心思想就是**不要尝试硬刚 NPC 问题**。