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

POJ 3207

BZOJ 1823

洛谷 P3209

BZOJ 2199

POJ 3683