2-SAT速成
本文只做总结性说明
2-SAT
2-SAT是k-SAT问题的一种，k-SAT问题在(k>=3)时已经被证明是NP完全问题
2-SAT问题定义比较简单
有n个布尔变量(x_1-x_n)。给出(m)个限制关系，每个关系最多只对两个变量进行限制。求一组取值使得满足所有限制。
这里的限制例如：选(A)必选(B) 或是 (A,B)至少选一个
解决方法
2-SAT问题所构成的图具有对称性
对于两个点来说
即若选(A)必选(B)，那么选(B)必选(A)
根据这种性质，前人总结出了一种方法
将一个点(A)拆为(A,A')
1.若选(A)必选(B)，那么从(A)向(B)连一条边
2.tarjan缩点(把时间从(O(NM))优化至(O(n)))
3.判断是否(A'A)是否在同一强联通分量中
对于需要输出方案的题目
4.根据缩完点的图，建出其反图
5.对反图进行拓扑排序
6.根据拓扑排序的顺序标记答案
经典模型
- 两者（A，B）不能同时取
那么选择了A就只能选择B’，选择了B就只能选择A’
连边A→B’，B→A’
- 两者（A，B）不能同时不取
那么选择了A’就只能选择B，选择了B’就只能选择A
连边A’→B，B’→A
- 两者（A，B）要么都取，要么都不取
那么选择了A，就只能选择B，选择了B就只能选择A，选择了A’就只能选择B’，选择了B’就只能选择A’
连边A→B，B→A，A’→B’，B’→A’
- 两者（A，A’）必取A
连边A’→A
(A'A)不能同时出现，选(A')必选(A)，故只能单独选(A)
例题
由简单到简单2333