下面的是从该网站上copy过来的，稍微改了一点，给出链接：http://hi.baidu.com/nondes/item/26dd0f1a02b1e0ef5f53b1c7
题意：有N个人玩剪刀石头布，其中有个人是裁判，其他人分为3组。 这3组中每个组分别出剪刀，石头和布。 裁判可以任意出3个中的一个。 现在有M个回合，每个回合从N个人中任意选出两个人来玩，并给出结果。 要求输出最早找出裁判的回合数，以及裁判的编号！ 还有可能无法确定，或者不可能出现这种结果。
思路：利用并查集可以建立起相对关系，但是问题出在裁判可以任意出招，也就是说通过裁判建立起来的任何关系都是不可靠的。 所以不能通过裁判来建立任何关系。
于是可以枚举裁判是哪一个，对有他参与的回合不予处理！ 接下来就是如何确定他是不是裁判！
假设当前某个人作为裁判，在他不参与的回合中出现了矛盾，那么这个人一定就不是裁判。
1.如果存在着一个真实的裁判，那么枚举他的时候不会出现矛盾，而枚举其他人的时候一定会出现矛盾。
2.如果有大于1个不出现任何矛盾的情况，则就是不能确定的！
3.而对于所有枚举都出现矛盾的时候，即所有小孩都不是裁判，则这是不可能的。因为如果出现矛盾，那么其中至少有一个“临时”裁判，枚举到他的时候就应该不出现矛盾！
怎么确定最早发现裁判的回合数：
对每一轮枚举，发现矛盾最早时刻是error[i]，那么确定裁判的回合数一定是max(error[i])。
对于处理并查集的时候，可以通过记录一个val[i]表示他与父亲节点的关系：
val[i]==0：表示他和父亲同组； val[i]==1：表示父亲所在的组能赢过他； val[i]==2：表示他能赢过父亲所在的组；
再附上从一个网站上看到的，自己修改了一点，后来找不到网址了，给出不了链接了。。。原作者原谅啊。。。
其实这题跟食物链完全一个磨子，同样三类食物，同样的互相制约关系。但这题有个judge，他可以出任意手势。
于是我们的做法是，枚举每个小孩为裁判，判断他为裁判时在第几句话出错error[i](即到第几句话能判断该小孩不是裁判)。
1. 如果只有1个小孩是裁判时，全部语句都是正确的，说明该小孩是裁判，那么判断的句子数即为其他小孩的error[i]的最大值。
2. 如果每个小孩为裁判时，都可以找到矛盾的语句，则他们都不是裁判，那么就是impossible。
3. 多于1个小孩为裁判时，没有找到矛盾的语句，就是Can not determine。
至于为什么判断的句子数是其他小孩的error[i]的最大值max，因为至少需要max行语句，才能使得其他小孩“做裁判”时找出矛盾的语句。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> /* AC 579ms 枚举+带权并查集，如何判断最后输出结果的时候比较难 */ using namespace std; const int maxn=510; int n,m,num;//num为枚举完所有人后，其中不矛盾的个数(即有多少个人"做裁判"时，剩下的数据中没有出现矛盾) int father[maxn]; int val[maxn]; //相对父节点的关系，平局:0,输:1(输给父节点),赢:2(赢了父节点) int error[maxn];//error[i]表示枚举i做裁判时，矛盾出现在第几行 char str[2010][20]; struct Node{ int a,b,c; //a<b,a>b,a=b，c存储的是b相对a的关系：平局:0,输:1,赢:2 }node[2010]; void init(){ for(int i=0;i<maxn;i++){ father[i]=i; val[i]=0; } } int find_root(int x){ if(father[x]==x) return x; int tmp=father[x]; father[x]=find_root(father[x]); val[x]=(val[x]+val[tmp])%3; return father[x]; } void Union(int x,int y,int fx,int fy,int c){ father[fy]=fx; val[fy]=(3-val[y]+c+val[x])%3; } //求每次询问时的a,b,c的值，存入node数组中 void abc(int j){ node[j].a=node[j].b=node[j].c=0; int len=strlen(str[j]),i; for(i=0;i<len;i++){ if(str[j][i]=='<'){ node[j].c=2; break; } else if(str[j][i]=='>'){ node[j].c=1; break; } //额，原本就直接写了个else。。。 else if(str[j][i]=='='){ node[j].c=0; break; } } for(int k=0;k<i;k++){ node[j].a*=10; node[j].a+=str[j][k]-48; } for(int k=i+1;k<len;k++){ node[j].b*=10; node[j].b+=str[j][k]-48; } } int main() { int a,b,c; int ans,round; //ans存储裁判的编号，round存储在第几行可判断出裁判 while(scanf("%d%d",&n,&m)!=EOF){ init(); memset(error,0,sizeof(error)); num=0; round=0; for(int i=1;i<=m;i++){ scanf("%s",str[i]); abc(i); } /* 我知道原本错哪里了啊，小孩的编号不仅仅只有一位数。。。如12<13，100<101。。。 */ for(int i=0;i<n;i++){ init(); //每次枚举之前都要初始化。。。 for(int j=1;j<=m;j++){ a=node[j].a; b=node[j].b; c=node[j].c; if(a==i || b==i) continue; int fa=find_root(a); int fb=find_root(b); if(fa==fb){ int t=(val[b]+3-val[a])%3; if(t!=c){ error[i]=j; break; } } else{ Union(a,b,fa,fb,c); } } } for(int i=0;i<n;i++){ round=max(round,error[i]); if(error[i]==0){ ans=i; num++; } } //只有一个小孩，当他作为裁判时，全部语句都正确，则他为裁判 if(num==1){ printf("Player %d can be determined to be the judge after %d lines ",ans,round); } //当有多个小孩，当他作为裁判时，全部语句都正确，则无法确定 else if(num>1){ printf("Can not determine "); } //所有小孩作为裁判时，语句都有矛盾的地方，即他们都不是裁判，显然不可能 else{ printf("Impossible "); } } return 0; }