2-SAT速成
程序员文章站
2022-09-08 07:52:40
本文只做总结性说明 2 SAT 2 SAT是k SAT问题的一种,k SAT问题在$k =3$时已经被证明是NP完全问题 2 SAT问题定义比较简单 有n个布尔变量$x_1 x_n$。给出$m$个限制关系,每个关系最多只对两个变量进行限制。求一组取值使得满足所有限制。 这里的限制例如:选$A$必选$ ......
本文只做总结性说明
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
上一篇: 晁错为汉朝做出了什么贡献?三大奇谋振兴了汉朝却覆灭了晁家!
下一篇: 漫画图片里面的搞笑故事