RainAir
My OI Blog
RainAir
2-SAT 学习笔记

定义

SAT

维基百科——Boolean_satisfiability_problem

2-SAT

SAT 的简化版本:每个等式中只有两个变量参与。
有 $n$ 个 $0/1$ 变量和 $m$ 个等式,每个等式形如 $x_i \text{op} x_j =k$,其中 $op$ 是一个位运算。
你要求出一组可行解。

求解

将每个 $x_i$ 拆成两个点 $x_{i,0}$ 和 $x_{i,1}$ 表示 $x$ 取值情况。
每个限制都能被转化为形如 如果 $x_a$ 为 $p$ 那么 $x_b$ 必须为 $q$ 这样的限制。对于这样的限制,我们建立一条 $x_{a,p}$ 到 $x_{b,q}$ 的单向边,表示选了 $a$ 必须选 $b$。
然后跑强连通分量,每个强连通分量内的点代表了这整个分量要一起选。显然如果一个点的两个状态都在一个强连通分量里那么就无解。
考虑如何构造方案:我们按照逆拓扑序依次考虑每个点,如果能选就将这个强连通分量选上,并且将选出的点的另一种状态的点所在的强连通分量都 ban 掉,这是贪心先选取对全图影响小的强连通分量。
其实在 tarjan 求强连通分量的时候有一个小性质:求出的强连通分量的编号越大,这个分量的拓扑序就越小。

建图

把常见的三种情况写一下。
1. 如果 $x=a$ 则 $y=b$
建边 $x_a \to y_b,y_{\lnot b} \to x_{\lnot a}$,意思是如果 $x$ 是 $a$ 则 $y$ 必须是 $b$ 成立,那么逆否命题($y$ 不是 $b$ 则 $x$ 不是 $a$) 也成立。
2. $x=a$ 或 $y=b$ 成立
建边 $x_{\lnot a} \to y_b,y_{\lnot b} \to x_a$。十分显然。如果一个不满足了那么另一个必须要满足。
3. $x=a$
建边 $x_{\lnot a} \to x_a$,这是情况 $2$ 的特殊形式($x=a$ 或 $x=a$ 成立)。
实际意义是如果选择了 $x_{lnot a}$ 就必须选择 $x_a$,也就无解了,所以会被强制选择 $x_a$。

例题

JSOI 2010 满汉全席

题意

$n$ 道菜,每道菜可以做成汉族口味和满族口味。$m$ 个评委,每个评委会对两道不同的菜有要求。要求都是某个菜要做成什么口味。问是否存在一种方案,使得每个评委至少有一个要求被满足。
$n \leq 100$,$m \leq 1000$,$T \leq 50$。

题解

满族口味为 $0$ ,汉族口味为 $1$,就是建图中的情况二。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/873
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

2-SAT 学习笔记
定义 SAT 维基百科——Boolean_satisfiability_problem 2-SAT SAT 的简化版本:每个等式中只有两个变量参与。 有 $n$ 个 $0/1$ 变量和 $m$ 个等式,每个等式形如 $x_i \text{op} x_j =k…
扫描二维码继续阅读
2019-10-12
标签
近期评论