复习2-sat小结
2-sat 就是用来解决像和平委员会这样的问题
即有很多只有两个取值的变量，且有一些形如"Ａ取１，Ｂ就取／不取１"的限制条件
问是否存在合法方案
首先基本的建图就是先拆点，每个点拆成(0,1)
对于限制条件A取１，Ｂ就取０，那么就从A1向B0连边
最终如果Ａ１和Ａ０在同一个强连通分量就无解
因为Ａ既是１又是０，显然不合法
对于输出方案
我们可以先拓扑排序
拓扑序大的先取出，因为它没有出边了，选它不会有影响，然后删除它的另一个取值所对应的点
然后可以用一个简单算法堆起来的算法得出方案
但是我们也可以对每个变量，取ｔａｒｊａｎ时所属连通块编号小的
为什么呢？
tarjan取连通块是从下到上的，那编号小的就是拓扑序大的
如果要求字典序最小解，那就只能暴力找了
从小到大枚举每个变量的取值，然后ｄｆｓ一遍看是否有变量既要取１又要取０
没有就合法
２－ｓａｔ第一题肯定是和平委员会
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1814
裸的2-sat，只是要输方案
bzoj1997＆＆poj3207
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1997
平面图判定
每条边不在外面就在里面，如果有交，就不能放在一侧，然后就是典型的2-sat了
poj2749
传送门：http://poj.org/problem?id=2749
二分距离，２－ｓａｔ判定
poj3678
传送门：http://poj.org/problem?id=3678
一道好题
xor好办
关键是a and b=1 就由a0向a1连边，b0->b1,a1->b1,b1->a1
a or b=0类似
bzoj2199
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2199
求最小字典序解，只能暴力
bzoj2215
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2215
写完这题就可以洗洗睡了，确实是一道坑爹愉悦的题
题解：http://blog.csdn.net/thy_asdf/article/details/50513475