浅谈2-SAT

用处

给 \(n\) 个 \(0/1\) 变量，其之间满足若关系，这些关系本质上可以化成：若 \(a_i\) 为 \(0/1\)，则 \(a_j\) 为 \(0/1\) 的若干命题，2-SAT 就是判断是否能够满足所有命题，并给出一组可行解（\(n^2\) 可得字典序最小的特解）。

一般解法

考虑建图，每个变量拆成真假两点，命题可以抽象出若干条如：若 \(i\) 则必须 \(j\) 形式的 \(i\to j\) 的边。如果 \(i\) 与 \(i\) 的逆否命题 \(\neg i\) 位于同一个强连通分量中，则无解，反之必定存在解，考虑怎么构造一组解。

强连通分量构成的图为一张 DAG，先给出结论：如果 \(i\) 所在强连通的拓扑序在 \(\neg i\) 的之后，则选 \(i\)。

感性理解：如果 \(i\) 的强连通拓扑序越后，则它能影响到的点更小，显然更优。

具体证明：反证法讨论每种情况，矛盾都很显然，注意抓住建出的图是具有对称性的一点思考。

一般实现为 tarjan 求强连通，注意 tarjan 是 dfs 顺序，相当于一个栈，出栈时顺序会倒一下，所以先到的强连通拓扑序越大。

一些常见建边

别人有总结，我觉得还是根据选 \(i\) 必选 \(j\) 的建边原则思考普适性要大一些。

一些题

题单，Part 1 不讲。

UVA1391 Astronauts

看似每个人有三个选项，实际上还是两个，所以直接2-SAT，\((i,j)\) 关系不好就是 \(i\to \neg j,\quad j\to \neg i\)。

P3513 [POI2011]KON-Conspiracy

发现是一个团（集合内全互相有边）和一个独立集（集合内任意都无边），考虑如果我们知道一组可行解，怎么变成其他解。不难发现，只能从团拿一个元素去独立集、独立集拿一个元素去团、团和独立集交换一对元素三者中选一个进行变换，模拟一下统计能有几种变换即可。

P3825 [NOI2017]游戏

对于 \(a,b,c\) 都是只能选两个值，但是 \(x\) 能选三个，这就不满足2-SAT了，但是我们可以枚举 \(x\) 是 \(a,b,c\) 中哪个来转换成 2-SAT 问题，但是发现 \(a\) 包括选 \(B,C\)，\(b\) 包括选 \(A,C\)，已经可以表示出 \(x\) 的所有车辆选择了，所以只用 \(2^d\) 枚举 \(a,b\) 中哪个就好了。

建边：对于一组 \((i,h_i,j,h_j)\) 如果 \(i\) 图和 \(h_i\) 车矛盾，则不建边。反之，如果 \(j\) 图与 \(h_j\) 矛盾，则不可选 \(h_i\)，所以 \(i \to \neg i\)，再反之，\(i\to j\) 且 \(\neg j \to \neg i\)。