djwj233 的博客

djwj233 的博客

2-SAT 学习笔记

posted on 2021-08-19 21:49:02 | under 笔记 |

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 问题

我们考虑建一张含有 $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 被求出的顺序可以看作是一个拓扑序的倒序。

根据上面我们的建图,一个没有出边的点的否定一定有出边,而有了出边就会对别的点造成影响。

因此,我们应该尽可能地选择没有出边的点。依次类推可以归纳证明选择一个拓扑序更大的点一定更优

检查部分的实现可以写得较为简单:

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("");

完整代码:

#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;
}

例题

简要题面:(摘自 OI-Wiki)

有 $k$ 盏灯,每盏灯是红色或者蓝色,但是初始的时候不知道灯的颜色。

有 $n$ 个人,每个人选择 $3$ 盏灯并猜灯的颜色,一个人猜对两盏灯或以上的颜色就可以获得奖品。

判断是否存在一个灯的着色方案使得每个人都能领奖,若有则输出一种灯的着色方案。

看到有多个变量,每个变量有 $2$ 种赋值,且赋值有约束时可以考虑 2-SAT。

为保证一个人领奖,我们需要在他猜错其中一盏灯时钦定他别的两盏灯必须猜对。

这样就可以 2-SAT 了。Code

我们注意到大多数的地图都只能使用 $2$ 种赛车,这启发我们使用 2-SAT。

但是还有 $d$ 幅所有赛车都能使用的地图,如果暴力枚举这 $d$ 幅地图的状态,复杂度将会达到 $\Theta(3^d(n+m))$,无法通过。

怎么优化呢?实际上我们对每幅 $x$ 地图只需枚举它是 $a$ 型或者 $b$ 型就可以了,这两种涵盖了所有三种赛车。

复杂度 $\Theta(2^d(n+m))$,可以通过,不过细节有点多。Code

核心思想就是不要尝试硬刚 NPC 问题