2-SAT速成

2018-03-01 07:48:45来源:cnblogs.com作者:自为风月马前卒人点击

分享

本文只做总结性说明

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

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台