hdu 4115 (2—SAT)
题意：两个人石头剪刀布，一个人的出法已确定，另一个人的出法有一定约束，某两次要相同或者不同，问你第二个人能否全部都不失败。
思路：根据Bob出的情况，我们可以确定每次Alice有两种方案。
R与P,S矛盾，P与R,S矛盾，S与R，P矛盾。
根据Bob出的情况建边：
如果Bob出的是石头(R)则Alice可以出石头或者布，就是~R与~P矛盾，~P与~R矛盾，建边~R—>P,~P—>R。
........................................
根据约束条件：
如果a，b两轮是一样的就是Ra与~Rb矛盾，Rb与~Ra矛盾，建边Ra—>Rb,Rb—>Ra,
........................................
如果a,b两轮不一样就是Ra与Rb矛盾，Rb与Ra矛盾，建边Ra—>~Rb,Rb—>~Ra,
.......................................
#include<stdio.h>#include<string.h>#include<stack>const int N=61000;using namespace std;int head[N],num,low[N],dfs[N],idx,ans,belong[N],ins[N];stack<int>Q;struct edge{int st,ed,next;}e[N*10];void addedge(int x,int y){e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;}void Tarjan(int u)//缩点 { int i,v; Q.push(u); ins[u]=1; low[u]=dfs[u]=idx++; 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]==1) low[u]=low[u]>dfs[v]?dfs[v]:low[u]; } if(dfs[u]==low[u]) { do { v=Q.top(); Q.pop(); ins[v]=0;//又忘了这个，调了半天 belong[v]=ans; }while(v!=u); ans++; } } int main(){int i,x,y,a[3],b[3],c,t,op=1,k,n,m;scanf("%d",&t);while(t--){memset(head,-1,sizeof(head));num=0;scanf("%d%d",&n,&m);k=3*n;for(i=1;i<=n;i++){a[0]=i;a[1]=a[0]+n;a[2]=a[1]+n;addedge(a[0],k+a[1]);addedge(a[0],k+a[2]);//R->非P，R->非Saddedge(a[1],k+a[0]);addedge(a[1],k+a[2]);//P->非R，P->非Saddedge(a[2],k+a[0]);addedge(a[2],k+a[1]);//S->非R，s->非R}for(i=1;i<=n;i++){a[0]=i;a[1]=a[0]+n;a[2]=a[1]+n;scanf("%d",&x);if(x==3)//Bob出的是剪刀{addedge(k+a[0],a[2]);//非R->Paddedge(k+a[2],a[0]);//非P->R}else{addedge(k+a[x],a[x-1]);addedge(k+a[x-1],a[x]);}}for(i=0;i<m;i++){scanf("%d%d%d",&x,&y,&c);a[0]=x;a[1]=a[0]+n;a[2]=a[1]+n;b[0]=y;b[1]=b[0]+n;b[2]=b[1]+n;if(c==0){addedge(a[0],b[0]);addedge(b[0],a[0]);addedge(a[1],b[1]);addedge(b[1],a[1]);addedge(a[2],b[2]);addedge(b[2],a[2]);}else {addedge(a[0],k+b[0]);addedge(b[0],k+a[0]);addedge(a[1],k+b[1]);addedge(b[1],k+a[1]);addedge(a[2],k+b[2]);addedge(b[2],k+a[2]);}}memset(dfs,-1,sizeof(dfs));idx=0,ans=0;memset(belong,0,sizeof(belong));memset(ins,0,sizeof(ins));for(i=1;i<=k+k;i++){if(dfs[i]==-1)Tarjan(i);}for(i=1;i<=n;i++){a[0]=i;a[1]=a[0]+n;a[2]=a[1]+n;if(belong[a[0]]==belong[a[0]+k])break;if(belong[a[1]]==belong[a[1]+k])break;if(belong[a[2]]==belong[a[2]+k])break;}printf("Case #%d: ",op++);if(i<=n)printf("no\n");else printf("yes\n");}return 0;}