题意：两个人石头剪刀布，一个人的出法已确定，另一个人的出法有一定约束，某两次要相同或者不同，问你第二个人能否全部都不失败。
思路：根据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->非S
addedge(a[1],k+a[0]);addedge(a[1],k+a[2]);//P->非R，P->非S
addedge(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->P
addedge(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;
}