「某讲稿」 2-SAT 学习笔记

写在前面

~~好孩纸写学习笔记要有格式~~

题目引入

就用 $2-SAT$ 模板趴，但其实感jio第二题更加经典

「Luogu P4782」【模板】2-SAT问题

题目背景

$2-SAT$ 问题模板

题目描述

有 $n$ 个布尔变量 $x_i$，另有 $m$ 个需要满足的条件，每个条件的形式都是 “$x_i$ 为 $true/false$ 或 $x_j$ 为 $true/false$ “。比如 “$x_1$ 为 $ture$ 或 $x_3$ 为 $false$ “、”$x_7$ 为 $false$ 或 $x_2$ 为 $false$”。$2-SAT$ 问题的目标是给每个变量赋值使得所有条件得到满足。

输入格式

第一行两个整数 $n$ 和 $m$，意义如体面所述。

接下来 $m$ 行每行 $4$ 个整数 $i\ a\ j\ b$，表示 “$x_i$ 为 $a$ 或 $x_j$ 为 $b$”$(a,b\in {0,1})$

输出格式

如无解，输出 IMPOSSIBLE；否则输出 POSSIBLE，下一行 $n$ 个整数 $x_i(x_i\in {0,1})$，表示构造出的解。

输入输出样例

输入样例 #1：

3 1
1 1 3 0

输出样例 #1：

POSSIBLE
0 0 0

说明/提示

$1\le n,m\le1e6$，前 $3$ 个点卡小错误，后面 $5$ 个点卡效率，由于数据随机生成，可能会含有 10 0 10 0 之类的坑

Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer $c (0 \leq c \leq 1)$. One Katu is solvable if one can find each vertex Vi a value $X_i (0 ≤ X_i ≤ 1)$ such that for each edge e(a, b) labeled by op and c, the following formula holds:
$X_a\ op\ X_b = c$
The calculating rules are:

Given a Katu Puzzle, your task is to determine whether it is solvable.

输入格式

The first line contains two integers $N (1 \leq N \leq 1000)$ and $M(0 \leq M \leq 1,000,000)$, indicating the number of vertices and edges.
The following M lines contain three integers $a (0 \leq a \lt N)$, $b(0 \leq b \lt N)$, $c$ and an operator op each, describing the edges.

输出格式

Output a line containing YES or NO.

输入输出样例

输入样例 #1：

4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

输出样例 #1：

YES
//此行纯粹是为了行号

说明/提示

$X_0 = 1, X_1 = 1, X_2 = 0$.

正文

$SAT$ 是 $satisfiability$ 的缩写，是一类适应性问题的简称，一般形式为 $k-$适应性问题，简称 $k-SAT$

$2-SAT$ 是 $k-SAT$ 的一种情况，因为当 $k>2$ 时 $k-SAT$ 问题是 $NP$ 问题，所以……

像上述题目一样，$2-SAT$ 形式一般为：给出 $n$ 个变量，以及 $m$ 个限制条件，每个限制条件形如 $(not)a_i\ op\ (not)a_j=0/1$，求是否存在对 $n$ 个变量的合法赋值方案，使 $m$ 个条件均得到满足。其中 $a_i,a_j\in {0,1}$，$op$ 可以是 $or,and,xor$ 等，也就是 $bool$ 类型运算，除了上述的类型外，貌似其他的不是很常见

判定方法

$2-SAT$ 问题的判定方法如下：

1、建立 $2n$ 个节点的有向图，每个变量的 $a_i$ 对应 $2$ 个节点，一般设为 $i$ 和 $i+n$

2、考虑每个条件，形如 “若 $a_i$ 为 $p$ 则 $a_j$ 必须为 $q$”，$p,q\in {0,1}$。建立 $i+p\times n \to j+q\times n$ 的单向边。当然，要注意的是，上述条件蕴含着它的逆否命题 “若 $a_j$ 为 $1-q$ 则 $a_i$ 必须为 $1-p$”，因此在建图的时候还应该建立 $j+(1-q)\times n\to i+(1-p)\times n$ 的单向边，也就是说，点数和边数都应是变量数和条件数的两倍，开数组，初始化的时候应特别注意

3、这个时候我们就可以用 $tarjan$算法求出有向图中所有的强连通分量

4、若存在 $i\in [1,n]$，满足 $i$ 和 $i+n$ 属于同一个强连通分量，则表明：若 $a_i$ 赋值为 $p$，则 $a_i$ 必须赋值为 $1-p$，显然矛盾，说明问题无解。否则题目一定有解。

时间复杂度 $O(n+m)$

来康个栗子

3 2
1 1 3 0
2 1 3 1

根据上述方法建图，可得：

不存在 $i,i+n$ 属于同一个强连通分量里，因此一定有解

而下图则由于存在 $i,i+n$ 属于同一个强连通分量而无解

合法方案

以下图为例

在 $tarjan$ 得出每个强连通分量的基础上，考虑如何构造合法方案

显然，在一个 $SCC$ 中，如果有一个变量确定了，那么它之后的一系列变量的值也确定了，因此我们可以考虑缩点来做。又因为，互为 “逆否命题”的有向边在图中成对出现，也就是说如果一个点的入度为 $0$，那么其对立点的出度即为 $0$，显然选择入度为 $0$ 的点会使其对立点被选，而选出度为 $0$ 的点则不会产生这种影响，如上图 $3,6$ 互为对立点，选 $6$ 不行，但是选 $3$ 满足

于是我们就可以缩点后建出反图，其中反图中的一个点即为原图的一个 $SCC$，然后我们在反图上执行拓扑排序即可，也就是说我们想要得到的是缩点后图的拓扑序的反序，具体实现留与读者自行思考，这里不做详细分析

考虑如何优化，不难发现，在 $tarjan$ 求 $SCC$ 的时候，由于 $tarjan$ 是递归进行的，最先得出的 $SCC$ 肯定是出度为 $0$ 的，第二出度再其次，其实已经很像或者说就是用递归求出了拓扑序的反序，即联通块的编号的顺序就是缩点后图的反序，直接根据联通块的编号判断贪心的取即可

对于点 $i$ 和 $i+n$，如果 $bl[i]\lt bl[i+n]$，也就是说 $i$ 所在的 $SCC$ 编号小于 $i+n$，此时取 $i$，否则取 $i+n$

例题选讲

「Luogu P4782」【模板】2-SAT问题

由于或的性质，只要在一侧不满足的情况下向另一侧满足的情况连接有向边表示限制即可

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 1000003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int head[N<<1],ver[N<<1],nxt[N<<1],n,m,t,num;
int bl[N<<1],St[N<<1],top,dfn[N<<1],low[N<<1],res;
bool vis[N],w[N];
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t;
}
inline void tarjan(rint k) {
    rint i,to;
    dfn[k]=low[k]=++num,St[++top]=k;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];
        if(!dfn[to]) tarjan(to),cmin(low[k],low[to]);
        else if(!bl[to]) cmin(low[k],dfn[to]);
    }
    if(dfn[k]==low[k]) {
        bl[k]=++res;
        while(St[top]!=k)
            bl[St[top]]=res,--top;
        --top;
    }
}
inline void dfs(rint k) {
    rint i,to;
    if(k>n) vis[k-n]=1,w[k-n]=1;
    else vis[k]=1;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i]>n?ver[i]-n:ver[i];
        if(!vis[to]) dfs(ver[i]);
    }
}
int main()
{
    rint i,x,y,vx,vy;
    n=read(),m=read();
    for(i=1;i<=m;i++) {
        x=read(),vx=read(),
        y=read(),vy=read(),
        add(y+(vy^1)*n,x+vx*n),//一侧命题为假时向另一侧命题为真连边表示限制
        add(x+(vx^1)*n,y+vy*n);
    }
    for(i=1;i<=(n<<1);i++)
        if(!dfn[i]) tarjan(i);
    for(i=1;i<=n;i++)
        if(bl[i]==bl[i+n]) {
            printf("IMPOSSIBLE");//无解
            return 0;
        }
    printf("POSSIBLE\n");
    for(i=1;i<=n;i++) printf("%d ",bl[i]>bl[i+n]);//根据反序或者说SCC编号
    return 0;
}

「NowCoder51271」 Katu Puzzle

$Solution’s\ Link$

「某讲稿」 2-SAT 学习笔记

写在前面

题目引入

「Luogu P4782」【模板】2-SAT问题

题目背景

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1：

输出样例 #1：

说明/提示

「NowCoder51271」 Katu Puzzle

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1：

输出样例 #1：

说明/提示

正文

判定方法

合法方案

例题选讲

「Luogu P4782」【模板】2-SAT问题

Code

「NowCoder51271」 Katu Puzzle

推荐题目

「Luogu P3825」[NOI2017]游戏解题报告

「CSP2019游记」

h^ovny

写在前面

题目引入

「Luogu P4782」【模板】2-SAT问题

题目背景

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1：

输出样例 #1：

说明/提示

「NowCoder51271」 Katu Puzzle

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1：

输出样例 #1：

说明/提示

正文

判定方法

合法方案

例题选讲

「Luogu P4782」【模板】2-SAT问题

Code

「NowCoder51271」 Katu Puzzle

推荐题目

「Luogu P3825」[NOI2017]游戏 解题报告

「CSP2019游记」

h^ovny

「Luogu P3825」[NOI2017]游戏解题报告