2-SAT学习笔记

首先安利一个博客:传送门

2-SAT介绍

给出若干布尔变量及一些关于其中两个布尔变量的限制,求是否可行,可行则给出方案。

算法介绍

建图

对每一个布尔变量拆为两个点,分别表示真和假。点之间的有向边表示一个被确定了,另一个也必须被确定;当一个变量的两个点都被确定时,产生矛盾,返回不可行。

限制的建边如下:

  • 两个变量不同为真

若一个变量为真,则另一个必为假。

aabb 表示两个变量的真,aa'bb' 表示假,后同。

ab,  baa \rightarrow b', \; b \rightarrow a'

  • 两个变量不同为假

若一个变量为假,则另一个必为真。

ab,  baa' \rightarrow b, \; b' \rightarrow a

  • 两个变量值相同

若一个为某一个值,另一个必为同样的值。

ab,  ba,  ab,  baa \rightarrow b, \; b \rightarrow a , \; a' \rightarrow b', \; b' \rightarrow a'

  • 两个变量值不同

就是限制一加上限制二。。。

算法过程

算法一:

对一个变量,先认为它是真,dfs 一遍后若出现矛盾,就认为它是假,若仍有矛盾,则返回不可行。

算法二(常用算法):

首先,2-SAT 的图有这样的特点:

若一个点被确定(选择),则其连出的点也被确定;若一个点被确定不选,则其父节点也不选。

由此,我们得出来这样的结论:

同一个强连通分量内的点,要么同时被选,要么同时被不选。

故我们对 2-SAT 建的图跑 Tarjan,若有一个变量的两个点在同一个强连通分量内,则返回不可行。

输出方案时,在 Tarjan 的基础上缩点,建立新图时,连边要连反向边,因为我们要传递的是不选择的标记,而不选择的标记是反向传递的(见前面的那条性质)。新图建完后,对图进行拓扑排序,具体的过程是:把入度为 00 的点放入栈(队列也行,因为取出顺序无所谓),每次取出一个节点(如果还没标记的话,后同)标记为选择,同时标记对应的点为不选择,从对应点开始 dfs,沿路均标记为不选择,对于原来取出的点,其连出的边指向的点入度减一(即相当于删除这条边),当出现入度为 00 的点时,放入栈中。最后按标记输出方案。

模版题

【JSOI 2010】满汉全席 - Luogu 4171题解)(不输出方案)

POJ 3683题解)(输出方案)