2-SAT

· · 个人记录

前置知识：有向图 Tarjan

k-SAT 问题

SAT 是适定性（Satisfiability）问题的简称。

k-SAT 问题就是给定 n 个 bool 变量和 m 个约束条件，每个条件形如 x_1\oplus x_2...x_k-1\oplus x_k=0/1（\oplus 表示任意逻辑运算），求是否有解，并构造解。当 k>2 时，k-SAT 问题是 NPC 问题。

2-SAT 建图

2-SAT 建图用到了种类并查集的思想，将每个点 i 拆成两个点 i 和 i+n，分别表示 x_i=1 和 x_i=0。

以 x_i=1 或 x_j=0 为例。若 x_i=0，则 x_j=0，从 i+n 向 j+n 连边，表示选了 i+n 就必须选 j+n。若 x_j=1，则 x_i=1，从 j 向 i 连边。

另一个例子：x_i=1，从 i+n 向 i 连边即可。

2-SAT 建图的对称性：

对于 i\leq n，设 inv_i=i+n,inv_{i+n}=i。容易发现，若 i 到 j 连边，则 inv_j 到 inv_i 也有边相连，因为原命题和逆否命题真假相同。因此可以用一个函数进行两次连边以简化代码：

void add(int x,int y){ne[++t]=he[x],to[t]=y,he[x]=t;}
void ins(int x,int y){add(x,y),add(y>n?y-n:y+n,x>n?x-n:x+n);}

Tarjan 求解 2-SAT

2-SAT 问题通常转化为强连通分量问题，用 Tarjan 求解。

用 Tarjan 求强连通分量，若 i 和 i+n 在同一个强连通分量，则无解（因为 i 和 i+n 只能选一个，而在同一个强连通分量的两个点只能同时选或不选）。否则有解，且可以构造方案。时间复杂度 O(n+m)。

构造方法：

Tarjan 的拓扑序是逆序，即从后求出的强连通分量可能到达先求出的强连通分量，从先求出的不可能到达后求出的。若 bl_i<bl_{i+n}，则 i 所在强连通分量先求出，从 i 不可能到达 i+n，因此选 i，否则选 i+n。

正确性证明：

根据以上构造过程，i 和 i+n 显然只会选一个，满足条件。

对于任意 x,y\leq2n，若从 x 能到达 y，则 bl_x\geq bl_y。根据 2-SAT 建图的对称性，从 inv_y 一定能到达 inv_x，则 bl_{inv_y}\geq bl_{inv_x}。若 x 被选而 y 没有被选，则 inv_x 没有被选而 inv_y 被选，bl_x<bl_{inv_x} 且 bl_y>bl_{inv_y}。所以 bl_{inv_x}>bl_x\geq bl_y>bl_{inv_y}，与 bl_{inv_y}\geq bl_{inv_x} 矛盾。因此对于任意被选的点 x，从 x 能到达的点都会被选，满足条件。

模板题：P4782 【模板】2-SAT 问题

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+3,M=4e6+3;
int he[N],to[M],ne[M],n,t,l[N],id,st[N],tp,bl[N],ct;
void add(int x,int y){ne[++t]=he[x],to[t]=y,he[x]=t;}
void ins(int x,int y){add(x,y),add(y>n?y-n:y+n,x>n?x-n:x+n);}
void tar(int x){
    int p=++id,i=he[x],j;
    for(l[st[++tp]=x]=p;i;i=ne[i])if(!l[j=to[i]])tar(j),l[x]=min(l[x],l[j]);else if(!bl[j])l[x]=min(l[x],l[j]);
    if(l[x]==p)for(++ct;bl[st[tp]]=ct,st[tp--]!=x;);
}
int main(){
    int m,i,j,u,v;
    scanf("%d%d",&n,&m);
    while(m--)scanf("%d%d%d%d",&i,&u,&j,&v),ins(u?i+n:i,v?j:j+n);
    for(i=1;i<=n*2;++i)if(!l[i])tar(i);
    for(i=1;i<=n;++i)if(bl[i]==bl[i+n])return puts("IMPOSSIBLE"),0;
    puts("POSSIBLE");
    for(i=1;i<=n;++i)printf("%d ",bl[i]<bl[i+n]);
    return 0;
}

习题（按难度排序）：

P4171 [JSOI2010]满汉全席

P5782 [POI2001]和平委员会

P3825 [NOI2017]游戏

P6378 [PA2010]Riddle（前缀优化建图）

CF1215F Radio Stations（前缀优化建图）

CF587D Duff in Mafia（前缀优化建图）

P6965 [NEERC2016]Binary Code（前缀优化建图）

CF1007D Ants（树剖+线段树+前缀优化建图）题解

DFS 求解 2-SAT

适用于某些有特殊限制，需要按特定顺序选点的 2-SAT 问题。时间复杂度最坏 O(nm)（从每个点开始对图 dfs 遍历一次），但随机数据下很快。

算法流程：从某个点开始 dfs，将经过的点 x 打上标记 b_x=1。若 dfs 到 x 时 b_{inv_x}=1，则搜索失败并在回溯时清空标记，否则成功。

代码（模板题数据较水，截止本博客发表此代码可 AC）：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+3,M=4e6+3;
int he[N],to[M],ne[M],n,t;
bool b[N];
void add(int x,int y){ne[++t]=he[x],to[t]=y,he[x]=t;}
void ins(int x,int y){add(x,y),add(y>n?y-n:y+n,x>n?x-n:x+n);}
bool dfs(int x){
    if(b[x>n?x-n:x+n])return 0;//搜索失败
    if(b[x])return 1;//搜过了就不用再搜了
    b[x]=1;//打标记
    for(int i=he[x];i;i=ne[i])if(!b[to[i]]&&!dfs(to[i]))return b[x]=0;//失败并清空标记
    return 1;//成功
}
int main(){
    int m,i,j,u,v;
    scanf("%d%d",&n,&m);
    while(m--)scanf("%d%d%d%d",&i,&u,&j,&v),ins(u?i+n:i,v?j:j+n);
    for(i=1;i<=n;++i)if(!b[i]&&!b[i+n]&&!dfs(i)&&!dfs(i+n))return puts("IMPOSSIBLE"),0;//若 i 和 i+n 都搜索失败则无解
    puts("POSSIBLE");
    for(i=1;i<=n;++i)printf("%d ",b[i]);
    return 0;
}

习题：

P3007 [USACO11JAN]The Continental Cowngress G

CF568C New Language（字典序贪心）

P5332 [JSOI2019]精准预测（bitset 优化，图是 DAG 所以不需要跑 Tarjan）

参考资料：OI Wiki 2-SAT