http://poj.org/problem?id=3678
给m条连接两个点的边，每条边有一个权值0或1，有一个运算方式and、or或xor，要求和这条边相连的两个点经过边上的运算后的结果是边的权值。问存不存在使所有边都符合条件的给点赋值的方法。
2-SAT的各种连法都有了。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 const int maxn=2010; 8 int n,m;char s[5]={}; 9 struct nod{ 10 int y,next; 11 }e[maxn*maxn]; 12 int head[maxn]={},tot=0; 13 inline void init(int x,int y){e[++tot].y=y;e[tot].next=head[x];head[x]=tot;} 14 int low[maxn]={},vis[maxn]={},dfn[maxn]={},cnt=0; 15 int sta[maxn]={},tai=0,bel[maxn]={},tn=0; 16 void tarjan(int x){ 17 low[x]=dfn[x]=++cnt;vis[x]=1;sta[++tai]=x; 18 for(int i=head[x];i;i=e[i].next){ 19 int y=e[i].y; 20 if(!dfn[y]){ 21 tarjan(y);if(low[x]>low[y])low[x]=low[y]; 22 } 23 else if(vis[y]&&dfn[y]<low[x])low[x]=dfn[y]; 24 } 25 if(low[x]==dfn[x]){ 26 int w;++tn; 27 do{ 28 w=sta[tai--]; 29 vis[w]=0;bel[w]=tn; 30 }while(w!=x); 31 } 32 } 33 int main(){ 34 scanf("%d%d",&n,&m);int x,y,v; 35 for(int i=1;i<=m;i++){//x+n 1 x 0 36 scanf("%d%d%d",&x,&y,&v);scanf("%s",s);++x;++y; 37 if(s[0]=='A'){ 38 if(v==1){ 39 init(x+n,y+n);init(y+n,x+n); 40 init(y,x+n);init(x,y+n); 41 }else {init(x+n,y);init(y+n,x);} 42 } 43 else if(s[0]=='O'){ 44 if(v==1){init(x,y+n);init(y,x+n);} 45 else{ 46 init(x,y);init(y,x); 47 init(x+n,y);init(y+n,x); 48 } 49 } 50 else{ 51 if(v==1){ 52 init(x,y+n);init(y+n,x); 53 init(x+n,y);init(y,x+n); 54 } 55 else{ 56 init(x+n,y+n);init(y+n,x+n); 57 init(x,y);init(y,x); 58 } 59 } 60 } 61 for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i); 62 int f=0; 63 for(int i=1;i<=n;i++){ 64 if(bel[i]==bel[i+n]){ 65 f=1;break; 66 } 67 } 68 if(f)printf("NO "); 69 else printf("YES "); 70 return 0; 71 }