zoj 3656 hdu 4421 (2—SAT)
题意：就是判断a数组是否存在，满足b数组的关系。
思路：把每个数有31位，每位上不是1就是0，所以就是SAT问题，刚开始尝试将点拆成500*31*2，一直MLE，就按位判断，就是31次判断，每次1000个点，，
SAT建图：
关系 添加弧
(1)A and B = 0 A->!B , B->!A
(2)A and B = 1 !A->A , !B->B
(3)A or B = 0 A->!A , B->!B
(4)A or B = 1 !A->B , !B->A
(5)A xor B = 0 A->B , B->A , !A->!B , !B->!A
//(A == 1 && B == 0 : A -> B, !B -> !A; A == 0 && B == 1 : !A -> !B, B -> A;)
(6)A xor B = 1 A->!B , B->!A , !B->A , !A->B
#include<iostream>#include<stdio.h>#include<stack>#include<string.h>const int N=2000;using namespace std;int head[N],num,low[N],dfs[N],belong[N],idx,ans,n;int b[510][510];bool ins[N];struct edge{int ed,next;}e[N*1000];void addedge(int x,int y){e[num].ed=y;e[num].next=head[x];head[x]=num++;}void p1(int i,int j,int w)//并关系{if(w&1)//i&j=1{addedge(n+i,i);addedge(n+j,j);}else//i&j=0{addedge(i,n+j);addedge(j,n+i);}}void p2(int i,int j,int w)//或关系{if(w&1){addedge(i+n,j);addedge(j+n,i);}else{addedge(i,i+n);addedge(j,j+n);}}void p3(int i,int j,int w)//异或关系{if(w&1){addedge(i,j+n);addedge(j,i+n);addedge(i+n,j);addedge(j+n,i);}else{addedge(i,j);addedge(j,i);addedge(i+n,j+n);addedge(j+n,i+n);}}stack<int>Q;void Tarjan(int u){int i,v;low[u]=dfs[u]=idx++;ins[u]=true;Q.push(u);for(i=head[u];i!=-1;i=e[i].next){v=e[i].ed;if(dfs[v]==-1){Tarjan(v);low[u]=low[u]>low[v]?low[v]:low[u];}else if(ins[v])low[u]=low[u]>dfs[v]?dfs[v]:low[u];}if(dfs[u]==low[u]){do{v=Q.top();Q.pop();ins[v]=false;belong[v]=ans;}while(v!=u);ans++;}}bool solve(){int i,j;for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(i&1&&j&1)//或p2(i,j,b[i][j]);else if(!(i&1)&&!(j&1))//并p1(i,j,b[i][j]);else//异或p3(i,j,b[i][j]);b[i][j]>>=1;}}idx=1;ans=1;memset(dfs,-1,sizeof(dfs));memset(ins,false,sizeof(ins));for(i=0;i<n+n;i++){if(dfs[i]==-1)Tarjan(i);}for(i=0;i<n;i++){if(belong[i]==belong[i+n])break;}if(i<n)return false;else return true;}bool judge(){for(int i=0;i<n;i++){if(b[i][i]!=0)return true;for(int j=i+1;j<n;j++)if(b[i][j]!=b[j][i])return true;}return false;}int main(){int i,j;while(scanf("%d",&n)!=-1){for(i=0;i<n;i++){for(j=0;j<n;j++)scanf("%d",&b[i][j]);}if(judge()){printf("NO\n");continue;}for(i=0;i<31;i++){memset(head,-1,sizeof(head));num=0;if(!solve())break;}if(i<31)printf("NO\n");else printf("YES\n");}return 0;}