2-SAT
2026-08-24
给出 n 个布尔变量 xi,以及 m 个条件。
每个条件形如 (i,a,j,b),表示 xi 为 a 或 xj 为 b 至少有一个成立。
需要判断是否有解,若有,给出一组合法构造。
为了方便,以下规定 xi 表示第 i 个变量为真,¬xi 表示第 i 个变量为假。
不难发现,条件其实跟推导差不多,也就是说,对于条件 (1,1,2,1),可以得到 ¬x1→x2,¬x2→x1。
运用这种限制的思想进行建图,得到一张有向图。
对于任何无解的情况,一定是因为 xi→⋯→¬xi 且 ¬xi→⋯→xi,也就是说,可以对原图的所有强连通分量进行判断,如果 xi 和 ¬xi 在同一个分量中,则无解。
一种合法构造是,对于每个 xi,¬xi,看它们所在联通块在拓扑排序中哪个更靠后取哪个。
构造合法证明
构造一定满足个 xi 只有一种取值,而在原图中,其实建图是对称的,也就是说如果 xi 和 xj 在同一个块里,则 ¬xi 和 ¬xj 在同一个块里。
接下来,我们以 x1 或 x2 为例,若取 ¬x1,怎么说明一定会取 x2?由于 ¬x1→x2,且 ¬x2→x1,也就是说 x2 在 ¬x1 后面,¬x2 在 x1 前面,又因为 x1 在 ¬x1 前面,即 x2 在 ¬x2 后面。
