2012年长春赛区B题，根据位运算的关系可以得到当某一个数的某一位取一个值时，跟其有相应运算关系的另一些数，就必须或者就不能取某些值，这样就可以利用2-sat问题解决，关于2-sat问题的加边技巧：
/*2-SAT问题，通俗的说就是有n对点（2n个点），从每对点中选出一个点，共选出n个点，而且要满足若干个这样的条件：某两点不能同时被选出。
设一对点为x、~x，如果a被选出则b一定要被选出，就在图中加有向弧(a,b)表示这种关系。那么如果a,b（a!=b,a!=~b）不能同时被选出，那么加两条有向弧(a,~b),(b,~a)。这样由图的对称性可以证明，2-SAT有解等价于任取x、~x，x、~x不在一个强联通分量中。
现在讨论一下特殊情况的意义。建图的过程中，如果a=b时，只用加一条有向弧(a,~a)；这样也是有意义的，可表示a不能出现（~a必须被选出）。如果a=~b时，会加两条有向弧(a,a),(b,b)，属于重边，无意义。这两种特殊情况都满足图的对称性：(a,~b)和(b,~a)同时存在，故不影响2-SAT的正确性。这样可以泛化一下满足条件，变成拓展的2-SAT：如果条件对应的若干个有向弧保证(a,~b)和(b,~a)同时存在，那么就可以转化最原始的2-SAT问题来解决。举个例子，如果有满足条件要求a必须出现，那么只需添加其对应的有向弧(~a,a)。这样2-SAT的应用范围就被大大增强了。（转载自http://blog.csdn.net/lethic/article/details/7803841）*/
我对2-sat加边的理解，比如说这道题中，如果a^b=0(a,b都表示一个二进制位)，那意味着a,b是相同的那么我们加边就是在a=1和b=1之间b=1和a=1之间和a=0和b=0之间以及b=0和a=0之间加一条边，对于这种情况我们加边的原则是如果a……那么b……或者是如果b……那么a……这样保证的是选一个就必须选另一个（这种也是包括了转载文章中所说的选一个就不能选另一个的，可以推理出来必须选的关系，比如a,b不能同时出现，也就意味着选a必须选~b选b必须选~a），再看另一种情况a&nb=1的时候，很多人的第一反应都是在a=1和b=1之间加一条边，再在b=1和a=1之间加一条边，我们说这么加边有一个前提就是一个是另一个成立的条件，比如说如果a出现那么b必须出现意味着b是a出现的条件，但是当a&b=1的时候，这个还成立吗？a是b的条件？还是b是a的条件？很显然都不是，也就是说，这个时候已经不符合加边的条件了，他们没有谁是依赖谁成立的关系，这两种情况都必须成立，那么这个时候怎么办呢？我们加这么一条边~a->a和~b->b，我们不妨看下面一个例子
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define N 1005 5 using namespace std; 6 int b[505][505]; 7 int head[N],t; 8 struct node 9 { 10 int v,next; 11 }; 12 node e[N*N*4]; 13 int stk1[N],stk2[N]; 14 int dfn[N],sc[N]; 15 int cnt0,cnt1,top1,top2; 16 void init() 17 { 18 t=0; 19 cnt0=cnt1=0; 20 top1=top2=0; 21 memset(head,-1,sizeof(head)); 22 memset(dfn,-1,sizeof(dfn)); 23 memset(sc,-1,sizeof(sc)); 24 } 25 void add(int u,int v) 26 { 27 e[t].v=v; 28 e[t].next=head[u]; 29 head[u]=t++; 30 } 31 void gabow(int u,int f) 32 { 33 dfn[u]=cnt0++; 34 stk1[top1++]=u; 35 stk2[top2++]=u; 36 int i,j,v; 37 for(i=head[u];i>=0;i=e[i].next) 38 { 39 v=e[i].v; 40 if(v==f) 41 continue; 42 if(dfn[v]==-1) 43 gabow(v,u); 44 else if(sc[v]==-1) 45 while(dfn[stk2[top2-1]]>dfn[v]) 46 top2--; 47 } 48 if(stk2[top2-1]!=u) 49 return; 50 top2--; 51 do 52 { 53 sc[stk1[--top1]]=cnt1; 54 }while(stk1[top1]!=u); 55 cnt1++; 56 } 57 int n; 58 void build(int p) 59 { 60 int i,j; 61 for(i=0;i<n;i++) 62 for(j=0;j<n;j++) 63 { 64 if(i==j) 65 continue; 66 if(i%2==1&&j%2==1) 67 { 68 if(b[i][j]&(1<<p)) 69 { 70 add(i+n,j);//i为0时j必须为1 71 add(j+n,i);//j为0时i必须为1 72 } 73 else 74 { 75 add(i,i+n);//i只能取0 76 add(j,j+n);//j只能取0 77 } 78 } 79 else if(i%2==0&&j%2==0) 80 { 81 if(b[i][j]&(1<<p)) 82 { 83 add(i+n,i);//i只能取1 84 add(j+n,j);//j只能取1 85 } 86 else 87 { 88 add(i,j+n);//i为1时j必为0 89 add(j,i+n);//j为1时i必为0 90 } 91 } 92 else 93 { 94 if(b[i][j]&(1<<p)) 95 { 96 add(i,j+n); 97 add(j,i+n); 98 add(i+n,j); 99 add(j+n,i); 100 } 101 else 102 { 103 add(i,j); 104 add(j,i); 105 add(i+n,j+n); 106 add(j+n,i+n); 107 } 108 } 109 } 110 } 111 bool solve() 112 { 113 int i,j,v; 114 for(i=0;i<n;i++) 115 if(b[i][i]) 116 return false; 117 for(i=0;i<32;i++) 118 { 119 init(); 120 build(i); 121 for(j=0;j<2*n;j++) 122 if(dfn[j]==-1) 123 gabow(j,-1); 124 for(j=0;j<n;j++) 125 if(sc[j]==sc[j+n]) 126 return false; 127 } 128 return true; 129 } 130 int main() 131 { 132 int i,j,k; 133 while(scanf("%d",&n)!=EOF) 134 { 135 for(i=0;i<n;i++) 136 for(j=0;j<n;j++) 137 scanf("%d",&b[i][j]); 138 if(solve()) 139 printf("YES\n"); 140 else 141 printf("NO\n"); 142 } 143 return 0; 144 }