下面的是从该网站上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=;
int n,m,num;//num为枚举完所有人后，其中不矛盾的个数(即有多少个人"做裁判"时，剩下的数据中没有出现矛盾)
int father[maxn];
int val[maxn]; //相对父节点的关系，平局:0,输:1(输给父节点),赢:2(赢了父节点)
int error[maxn];//error[i]表示枚举i做裁判时，矛盾出现在第几行
char str[][]; struct Node{
int a,b,c; //a<b,a>b,a=b，c存储的是b相对a的关系：平局:0,输:1,赢:2
}node[]; void init(){
for(int i=;i<maxn;i++){
father[i]=i;
val[i]=;
}
} 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])%;
return father[x];
} void Union(int x,int y,int fx,int fy,int c){
father[fy]=fx;
val[fy]=(-val[y]+c+val[x])%;
}
//求每次询问时的a,b,c的值，存入node数组中
void abc(int j){
node[j].a=node[j].b=node[j].c=;
int len=strlen(str[j]),i;
for(i=;i<len;i++){
if(str[j][i]=='<'){
node[j].c=;
break;
}
else if(str[j][i]=='>'){
node[j].c=;
break;
}
//额，原本就直接写了个else。。。
else if(str[j][i]=='='){
node[j].c=;
break;
}
}
for(int k=;k<i;k++){
node[j].a*=;
node[j].a+=str[j][k]-;
}
for(int k=i+;k<len;k++){
node[j].b*=;
node[j].b+=str[j][k]-;
}
}
int main()
{
int a,b,c;
int ans,round; //ans存储裁判的编号，round存储在第几行可判断出裁判
while(scanf("%d%d",&n,&m)!=EOF){
init();
memset(error,,sizeof(error));
num=;
round=;
for(int i=;i<=m;i++){
scanf("%s",str[i]);
abc(i);
}
/*
我知道原本错哪里了啊，小孩的编号不仅仅只有一位数。。。如12<13，100<101。。。
*/
for(int i=;i<n;i++){
init(); //每次枚举之前都要初始化。。。
for(int j=;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]+-val[a])%;
if(t!=c){
error[i]=j;
break;
}
}
else{
Union(a,b,fa,fb,c);
}
}
}
for(int i=;i<n;i++){
round=max(round,error[i]);
if(error[i]==){
ans=i;
num++;
}
}
//只有一个小孩，当他作为裁判时，全部语句都正确，则他为裁判
if(num==){
printf("Player %d can be determined to be the judge after %d lines\n",ans,round);
}
//当有多个小孩，当他作为裁判时，全部语句都正确，则无法确定
else if(num>){
printf("Can not determine\n");
}
//所有小孩作为裁判时，语句都有矛盾的地方，即他们都不是裁判，显然不可能
else{
printf("Impossible\n");
}
}
return ;
}