POJ 2912 Rochambeau（种类并查集+枚举）

题目大意：n个人玩，玩石头剪刀布游戏，其中1人是裁判，剩下的n-1个人分为3组，他们商量好了，相同组的人每次都出相同的手势，不同组的人是不同的，而裁判是随机出的。给出m个结果，判断那个是裁判。

解题思路：其实跟食物链差不多，也是分三组0、1、2，0吃1，1吃2，2吃0。裁判由于可以任意出，所以可能属于任意一个集合，所以有裁判参与的回合不考虑。所以要枚举0~n-1号选手，比如枚举到编号为x的选手时，就忽略跟x有关的信息，判断剩下的信息是否有矛盾，如果没有则sum+1。如果最后sum=0那么就是“Can not determine”；sum>1则是"Impossible"；sum=1的话就输出是裁判的那个人，关于从第几个信息之后可以判断他是裁判，那就是剩下的人出问题的地方取最大值。因为只有否定了其它所有人，才能确定谁是裁判。

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int N=1e4+5;
 6 
 7 int root[N],val[N];
 8 
 9 struct node{
10     int a,b,c;
11 }arr[N];
12 
13 int find(int x){
14     if(root[x]==x)
15         return x;
16     int tmp=find(root[x]);
17     val[x]=(val[x]+val[root[x]])%3;
18     return root[x]=tmp;
19 }
20 
21 int main(){
22     int n,m;
23     while(~scanf("%d%d",&n,&m)){
24         for(int i=1;i<=m;i++){
25             char c;
26             scanf("%d%c%d",&arr[i].a,&c,&arr[i].b);
27             if(c=='=')    arr[i].c=0;
28             if(c=='<')    arr[i].c=2;
29             if(c=='>')    arr[i].c=1;
30         }
31         bool flag;
32         int line=0,sum=0,ans;
33         //枚举0~n-1 
34         for(int i=0;i<n;i++){
35             //初始化 
36             memset(val,0,sizeof(val));
37             for(int j=0;j<n;j++)
38                 root[j]=j;
39             flag=false;
40         
41             for(int j=1;j<=m;j++){
42                 int a=arr[j].a,b=arr[j].b,c=arr[j].c;
43                 if(a==i||b==i)
44                     continue;
45                 int t1=find(a);
46                 int t2=find(b);
47                 if(t1==t2){
48                     if((val[a]+c)%3!=val[b]){
49                         //所有出问题的地方取最大值 
50                         line=max(line,j);
51                         flag=true;
52                         break;
53                     }
54                 }
55                 else{
56                     root[t2]=t1;
57                     val[t2]=(val[a]-val[b]+c+3)%3;
58                 }
59             }
60             //没有矛盾 
61             if(!flag){
62                 sum++;
63                 ans=i;
64             }
65         }
66         //判断sum的个数 
67         if(sum==0)
68             puts("Impossible");
69         else if(sum>1)
70             puts("Can not determine");
71         else
72             printf("Player %d can be determined to be the judge after %d lines
",ans,line);
73     }
74     return 0;
75 }