2-sat 问题

lingfunny · 2022-06-13 19:22:17 · 个人记录

2-sat 问题

定义¶

2-SAT，简单的说就是给出 个集合，每个集合有两个元素，已知若干个 ，表示 与 矛盾（其中 与 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。

来源 OI-wiki

简而言之，解决的问题就是形如有一些 bool 型变量，和一些限制条件，限制条件形如 \text{if [condition-1] then [condition-2]}。此时由 \text{condition-1} 向 \text{condition-2} 连一条有向边表示该限制条件，如果最后发现对于某个变量，由 \text{True} 可推向 \text{False}，由 \text{False} 可以推向 \text{True}，换句话说 \text{True} 和 \text{False} 强连通，则无解。可以用 Tarjan 算法解决该类问题。

输出方案见 OI-wiki 并结合手模思考。

1. “一些” bool 型变量不一定是 O(n) 个，“一些”限制条件不一定是 O(m) 个，可以设计合理状态表示以解决问题。例如 CF1697F. Too Many Constraints。
2. 限制条件不一定是裸的 \text{if a = True then b = False}，可以自己想办法转化成左边这种条件。常见的如 \text{a = True} 转成 \text{if a = False then a = True}。例如洛谷 P4782 【模板】2-SAT 问题。
3. 主要思想就是把复杂问题转成若干个 bool 型变量及一些限制条件。例如上面两个例如。

别的

1. 取值型问题一般状态设计是变量 x\ge k。形如 x=k 的状态设计不好做，因为默认了 x 的若干个状态中必须有一个为 \text{True}，然而实际建图中无法建出这样的限制条件，也可能是我太菜了所以建不出。

完结。