【OI之路】03图论算法-8-2-SAT

差分约束题目直观版:Tag-2-SAT
经典论文:由对称性解2-SAT问题

不错的入门教程:csdn-jarjingx
(不得不说,超级良心!)

话说2-sat问题好像是有很多种解法的,但我比较喜欢tarjan

正经说细节

  1. 如果要固定,某一个变量必须取某个值
    可以用一条单向边连接,表示如果选择了非法值,会导致矛盾
  2. 如果题目要求输出方案
    在scc缩点以后,不难发现,因为是个dag
    任意时刻一定会有出度为0的点

明确:缩点以后,边的关系就是,如果选择则必须传递选择
如果我每次选择一个之前没选择而且出度为0的节点,
那么一定是无害的(不选择它就不一定了)
此时把对立的节点(由原本的逻辑关系产生,一定只有唯一一个,否则应合并,因为只有二元)定为不选择
那么因为搞的是出度=0,可以在反图上跑拓扑

不过还有一个性质,能省去代码复杂度,不需要建立反图
因为tarjan求scc的时候,编号是自下而上的(不了解的请博客中搜索“简单连通性问题”)
不难发现,对于两个上下的scc之间,下面那个编号小,
恰好拓扑序也是在上面之前
所以可以根据两个对立scc的编号,直接确定选择与否(编号小,就选择)
相当优美简洁

练习

Caioj1405
聚会
Poj3207
Panda’s Trick
Bzoj1997
Planar
Poj3683
Priest John’s Busiest Day

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/ef65.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%