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的话就输出是裁判的那个人，关于从第几个信息之后可以判断他是裁判，那就是剩下的人出问题的地方取最大值。因为只有否定了其它所有人，才能确定谁是裁判。

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 const int N=1e4+;

 int root[N],val[N];

 struct node{

     int a,b,c;

 }arr[N];

 int find(int x){

     if(root[x]==x)

         return x;

     int tmp=find(root[x]);

     val[x]=(val[x]+val[root[x]])%;

     return root[x]=tmp;

 }

 int main(){

     int n,m;

     while(~scanf("%d%d",&n,&m)){

         for(int i=;i<=m;i++){

             char c;

             scanf("%d%c%d",&arr[i].a,&c,&arr[i].b);

             if(c=='=')    arr[i].c=;

             if(c=='<')    arr[i].c=;

             if(c=='>')    arr[i].c=;

         }

         bool flag;

         int line=,sum=,ans;

         //枚举0~n-1

         for(int i=;i<n;i++){

             //初始化

             memset(val,,sizeof(val));

             for(int j=;j<n;j++)

                 root[j]=j;

             flag=false;

             for(int j=;j<=m;j++){

                 int a=arr[j].a,b=arr[j].b,c=arr[j].c;

                 if(a==i||b==i)

                     continue;

                 int t1=find(a);

                 int t2=find(b);

                 if(t1==t2){

                     if((val[a]+c)%!=val[b]){

                         //所有出问题的地方取最大值

                         line=max(line,j);

                         flag=true;

                         break;

                     }

                 }

                 else{

                     root[t2]=t1;

                     val[t2]=(val[a]-val[b]+c+)%;

                 }

             }

             //没有矛盾

             if(!flag){

                 sum++;

                 ans=i;

             }

         }

         //判断sum的个数

         if(sum==)

             puts("Impossible");

         else if(sum>)

             puts("Can not determine");

         else

             printf("Player %d can be determined to be the judge after %d lines\n",ans,line);

     }

     return ;

 }

巴特西

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

最新文章

热门文章