2-SAT

2-SAT是求解满足性问题的算法.
实际测下来发现对于如何转成图论问题要求有点高,但是代码非常好写.

先把2-SAT转成图论问题:有 $2n$ 个点,前n个表示该点为假的时候的连边情况,后面n个点是该点为真的时候的情况.令有向边 $a\to b$ 的意义是选 $x$ 就必须选 $y$ .

i,j不能同时选 :选了 $i$ 就要选 $j’$ ,选 $j$ 就要选 $i’$ .故 $i→j’,j→i’$ .一般操作即为 $a_i\mathrm{xor} a_j=1$

i,j必须同时选 :选了 $i$ 就要选 $j$ ,选 $j$ 就要选 $i$ .故 $i→j,j→i$ .一般操作即为 $a_i\mathrm{xor} a_j=1$

i,j任选一个 :选了 $i$ 就要选 $j’$ ,选 $j$ 就要选 $i’$ .选 $i’$ 就要选 $j$ ,选 $j’$ 就要选 $i$ .故 $i→j’,j→i’,i’→
j,j’→i$ .一般操作即为 $a_i\mathrm{or}a_j=1$

i必须选 :直接 $i’→i$ ,可以保证无论怎样都选 $i$ .一般操作为给出的 $a_i=1$ 或 $a_i\ \mathrm{and}\ a_j=1$

所以对于条件 a为真或b为真 ,要把刚好满足的进行连边,也就是说,如果a真,后面b无论怎样都满足的时候不用连边,所以连 a->b+n 表示a假的时候b为真,以及 b->a+n 表示b为假的时候a必须为真.