最近看到一个很有意思的问题——2-sat问题，其基本定义就是说有n个布尔变量，给定m组变量之间的关系，每组最多只包含两个变量，求一种方案使得各个关系均满足。
解法：如果去掉“每组最多只包含两个变量”的条件，那么它就成了NPC问题，但是2-sat却有着非常巧妙的多项式解——将n个布尔变量表示成2n个点，分别表示该变量为真或为假。将必须同时选的两个点之间连上一条边；这样在这个图的一个强连通分量内的点就是必须都选的，如果一个强连通分量包含了x与!x，那么这个2-sat显然是无解的，否则一定可以根据拓扑序来选定一些点使该2-sat成立。
推荐两篇论文：华东师大一附中赵爽的《2-sat解法浅析》和《由对称性解决2-sat问题》，有关算法复杂度分析，具体实现，正确性证明可以参考论文。在此向论文作者致敬！！
下面是一些2-sat的题目（刷了很久才搞完，弱炸了T T）：
poj3207 Ikki's Story IV - Panda's Trick:
在圆上给n个点，之间连了一些边，每条边要么在里面，要么在外面，要求判断这些边是否一定有交点。“每条边要么在里面，要么在外面”，可以根据这个建立2-sat模型。枚举任意两条边，如果有交点那么就说明不能同时为里面或者外面，根据这个建图，再跑一遍模板就可以了。
poj3678 Katu Puzzle
真·模板题。给定一些两个变量的关系（and,or,not等），要求它们成立。直接根据关系建图，再跑一遍模板就可以了。
poj3683 Priest John's Busiest Day
给定一些区间，要求在它们的头或尾各选一个固定长度的子区间，并且各个子区间不能相交，求是否可行并给出一组可行的方案。根据“每个区间都必须在头或在尾选一个固定的区间”建立2-sat模型，跑模板即可。ps 其实这道题的核心不在2-sat，而是判断两个区间是否相交…………我写得无比复杂，后来终于发现可以根据区间端点的差值就可以做了……ps ps 2:00-2:30 2:30-3:00这两个区间没有交集，被坑了一次。
poj3648 Wedding
相当无语的题……有n对夫妻参加一次婚礼，它们和新郎新娘分别坐在桌子两边，要求夫妻（包括新郎新娘）不能坐在一端，且它们之间有些有通奸关系（同性和异性的都可能），有通奸关系的两人不能同时坐在新娘的对面。求是否可行和可行解。夫妻不能同时选在一边，有通奸关系的两人至少有一人在新娘这边。根据这个关系建图就可以做了。ps 被坑爆了，一开始以为n对都是新婚的…………后来看对题了又没想到新郎新娘也会有通奸关系………………相当无语………………什么婚礼啊………………………………
poj2723 Get Luffy Out
给出n对钥匙和m扇门，每扇门有两把锁，每种类型的锁必须要对应的钥匙才能打开（一一对应，且每种钥匙只有一把）；每扇门只需要开启一把锁就可以打开；每对钥匙只要用掉其中一把就不能用另一把；门必须按顺序打开；求最多能开多少扇门。二分答案，就变成了检验这些钥匙能否按顺序打开k扇门。每扇门如果不用开第一把锁（即不使用能开第一把锁的钥匙），就必须开第二把锁（即使用能开第二把锁的钥匙）；每对钥匙如果用掉一把，就不能用另一把。根据钥匙建图就可以检验了。ps 被坑了一次，检验答案k的时候只需要为前k扇门建边，但是要为所有的钥匙对建边。
poj2749 Building roads
有n个牛棚，两个交换站。每个牛棚必须建一条到某一个交换站的边，两个交换站之间也有一条边。某些牛棚不能被连在同一个交换站上，某些必须连在同一个交换站上。距离定义为曼哈顿距离。求牛棚之间距离最大值的最小值。二分最大值u，根据每两个牛棚之间的距离和给出的关系进行一些制约（如两个牛棚到交换站1的距离大于u，那么它们就不能被同时连在左边等），细节较繁琐，反正我写了180+行，有高手100行之内搞定的…………没办法，本人太弱了TT。ps 这题最开始数组开小了（应该是2*n^2），但是交上去却是WA而不是RE…………害得我搞了好久…………
最后，附上本人弱爆的模板，望各路神牛批评指出缺陷：
View Code 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 #define _y(x) (x<<1) 8 #define _n(x) (x<<1|1) 9 10 const int maxn=2010; 11 const int maxm=4000010; 12 13 struct node 14 { 15 int end; 16 node *next; 17 }edge[maxm],*head[maxn],*p; 18 19 int dfn[maxn],low[maxn],stk[maxn],color[maxn],n,colo,idx,all,top; 20 bool inS[maxn]; 21 22 inline void add_edge(int x,int y) 23 { 24 p=&edge[++all],p->end=y,p->next=head[x],head[x]=p; 25 } 26 27 void tarjan(int u) 28 { 29 dfn[u]=low[u]=++idx; 30 inS[stk[++top]=u]=true; 31 for (node *p=head[u];p;p=p->next) 32 if (!dfn[p->end]) 33 { 34 tarjan(p->end); 35 low[u]=min(low[u],low[p->end]); 36 } 37 else if (inS[p->end]) 38 { 39 low[u]=min(low[u],dfn[p->end]); 40 } 41 if (low[u]==dfn[u]) 42 { 43 int v;++colo; 44 do 45 { 46 inS[v=stk[top--]]=false; 47 color[v]=colo; 48 } while (u!=v); 49 } 50 } 51 52 int main() 53 { 54 int x,y,z,m; 55 char op[5]; 56 scanf("%d%d",&n,&m); 57 while (m--) 58 { 59 scanf("%d%d%d%s",&x,&y,&z,op),++x,++y; 60 if (op[0]=='A') 61 { 62 if (z) 63 { 64 add_edge(_y(x),_y(y)); 65 add_edge(_y(y),_y(x)); 66 add_edge(_n(x),_y(x)); 67 add_edge(_n(y),_y(y)); 68 } 69 else 70 { 71 add_edge(_y(x),_n(y)); 72 add_edge(_y(y),_n(x)); 73 } 74 } 75 else if (op[0]=='O') 76 { 77 if (z) 78 { 79 add_edge(_n(x),_y(y)); 80 add_edge(_n(y),_y(x)); 81 } 82 else 83 { 84 add_edge(_n(x),_n(y)); 85 add_edge(_n(y),_n(x)); 86 add_edge(_y(x),_n(x)); 87 add_edge(_y(y),_n(y)); 88 } 89 } 90 else if (op[0]=='X') 91 { 92 if (z) 93 { 94 add_edge(_y(x),_n(y)); 95 add_edge(_y(y),_n(x)); 96 add_edge(_n(y),_y(x)); 97 add_edge(_n(x),_y(y)); 98 } 99 else 100 { 101 add_edge(_y(x),_y(y)); 102 add_edge(_y(y),_y(x)); 103 add_edge(_n(x),_n(y)); 104 add_edge(_n(y),_n(x)); 105 } 106 } 107 } 108 x=n<<1|1; 109 for (int i=2;i<=x;++i) 110 if (!dfn[i]) 111 tarjan(i); 112 for (int i=1;i<=n;++i) 113 if (color[_y(i)]==color[_n(i)]) 114 { 115 puts("NO"); 116 return 0; 117 } 118 puts("YES"); 119 return 0; 120 }
转载于:https://www.cnblogs.com/stickjitb/archive/2013/02/26/2933286.html
