柒葉灬 的博客

柒葉灬 的博客

2-sat

posted on 2019-09-04 15:42:16 | under 专题总结 |

2-sat


一个点只有选(1),和不选(0)两种状态,

且关系是两两给出的,

就是求若干个 $ A[a_i]\ \ opt\ \ A[b_i] = B[c_i]$

其中opt可以是 $ xor\ \ or \ \ and $ ,

网上有更详细的介绍


使用:连边,tarjan(同时完成拓扑),判断。


重点:连边的时候一定要记住,2-sat满足边的对称性

意思是边一定要成对出现,比如说 $ID(a,1)$ 连了一条边,

一定要对应 $ID(a,0)$ 也有相应的边连。

例题:专题I 剪刀石头布。

这题里面要求两个局面出的一样,

不仅要判断选的时候另一边选,

同时也要判断不选的时候另一边也不选。