2-SAT !

2-SAT !

想知道2-SAT是什么一定要先知道SAT问题是什么:
适定性问题 Satisfiability
适,就是合适,定,就是确定,适定性问题通俗的说就是确定是否可以满足所有的条件?或者说就是确定一个满足所有条件的方案。
取英文前三个字母,即SAT问题
通俗的sat问题表述一般是这样的:有很多个集合,每个集合里面有若干元素,现给出一些取元素的规则,要你判断是否可行,可行则给出一个可行方案。如果所有集合中,元素个数最多的集合有k个,那么我们就说这是一个k-sat问题,同理,2-sat问题就是k=2时的情况。

我们从一个例题说起:
HDU 1814

题目大意:一国有n个党派,每个党派在议会中都有2个代表,现要组建和平委员会,要从每个党派在议会的代表中选出1人,一共n人组成和平委员会。已知有一些代表之间存在仇恨,也就是说他们不能同时被选为和平委员会的成员,现要你判断满足要求的和平委员会能否创立?如果能,请任意给出一种方案。

样例输入:
3 2
1 3
2 4
输出:
1
4
5

这个问题可以被简化为:有n个组,第i个组里有两个节点Ai, Ai’。需要从每个组中选出一个。而某些点不可以同时选出(称之为不相容)。任务是保证选出的n个点都能两两相容。
我们可以初步构图:
如果Ai与Aj不相容,那么如果选择了Ai,必须选择Aj’;
同样,如果选择了Aj,就必须选择Ai’。
Ai -> Aj’
Aj -> Ai’
这样的两条边对称

我们在这里不喵的拿样例引题:

根据我们构图的定义来说,在这样一个图内,我们选择1就一定要选择4,选择2就一定要选择3,而5和6可以任意选择
那么我们如果按字典序来查找选择,就可以得到1-4-5这个答案了

至此,我们得到了第一种解法
枚举每一对尚未确定的Ai, Ai’,任选1个,推导出相关的组,若不矛盾,则可选择;否则选另1个,同样推导。若矛盾,问题必定无解。
这个解法已经可以解决例题了!

但是我们还有一些更喵的优化
如果我们再仔细认识这个图,就会发现,对于一个强连通分量里的点,它们的是否选择是一样的,所以就可以进行强连通分量缩点,对新图(得到的DAG)再判断。
判断可行性:
枚举每一对Ai和Ai’,如果它们在一个强连通分量里即不可行
接下来我们要做的就是在新图中进行选择:对新图做一个拓扑排序,按自底向上的顺序,标记选择和不选择,把不选择的标记逆向传递即可。
为什么呢?

对于原图来说,我们的连边是具有对称性的,所以对于缩点后的新图也是一样的。
1、假设新图中两个点S1、S2,分别包含A1和A1’,那么S1和S2就是对称的点,里面包含的点也是对称的。
2、对于对称的S1和S2,S1的后继节点和S2的前驱节点是对称的。
对于新图中的点,记录一下每个点的矛盾点(含有Ai的点的矛盾点是含有Ai’的点)
考虑若按拓扑序从前往后选择,然后标记选择和不选择,这看起来是合理的,那么让我们来看这个例子(为原图):

首先找到A标记选择,A’不选择,然后B选择,B’选择,这矛盾了,可是原图是有解得啊!因为A是否选择对图的影响太大了,所以我们假如倒拓扑序,先选对原图影响小的A’,A标为不选再选择B,B’标为不选即可啊
所以我们就会选择倒着存图然后正着拓扑呗~

至此,我们得到了第二种算法,它是在第一个算法的基础上进行了缩点优化,并提前判断了是否无解
它的步骤是:
1、构图
2、求强连通分量、缩点
3、判断是否有解(无解直接退出即可)
4、对新图topo(新图存边时反着存,便于传递不选择标记)
5、进行选择

紧接着,不知道有没有人能发现,我们在对缩点后的图进行topo后,最终是倒着选择的,那么我们只要对于每一对Ai,Ai’选择topo序在后面的即可
然后听说:Tarjan 算法所求的强连通分量就是按拓扑序的逆序得出的
所以我们连建图和topo都省了,直接判断:
对于每个变量x ,让x 所在的强连通分量的拓扑序在x’ 所在的强连通分量之后,那么 x 为真

最终,我们得到了时间复杂度无敌的算法3
构图后缩点即可完成全部任务!

微暴力代码:
hdu 1814

带Tarjan代码(解法3):

1+

发表评论

电子邮件地址不会被公开。 必填项已用*标注