poj2912 带权并查集

题意：多个人玩石头剪刀布，每个人提前选定了自己出哪个手势，而其中有一种特殊的人他可以随意出什么手势，问是否能够从给出的一系列石头剪刀布游戏中判断出哪个是特殊的，可以从第几局游戏中判断出来。

首先按照食物链那题的做法，定 0,1,2 做为三种手势就可以了，不过由于判断是哪个人比较麻烦，不知道哪个人的选择是无效的，就不知道那几次游戏是不正确不能加入并查集的，因此就直接暴力枚举每个人是否为特殊的人，对于涉及这个人的所有游戏都不进行并查集操作，看剩下的游戏中是否会有矛盾，如果有就说明这个人不是特殊的人，否则他就可能是。最后如果只有一个人可能是，就可以判读出来，而判断出来的局数，就是枚举其他所有人出现矛盾的游戏场次的最大值，因为只有否定完其他所有人才能确定这个人是特殊的。

 #include<stdio.h>

 #include<string.h>

 const int maxm=;

 int fa[maxm],num[maxm],wa[maxm];

 struct ques{

     int a,b,c;

 }q[];

 void init(int n){

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

         fa[i]=i;

         num[i]=;

     }

 }

 int find(int x){

     int r=x,t1,t2,c=;

     while(r!=fa[r]){

         c+=num[r];

         r=fa[r];

     }

     while(x!=r){

         t1=fa[x];

         t2=c-num[x];

         num[x]=c%;

         fa[x]=r;

         c=t2;

         x=t1;

     }

     return r;

 }

 int main(){

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF){

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

             char c;

             scanf("%d",&q[i].a);

             c=getchar();

             while(c!='='&&c!='<'&&c!='>')c=getchar();

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

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

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

             scanf("%d",&q[i].b);

         }

         memset(wa,-,sizeof(wa));

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

             init(n);

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

                 if(q[j].a==i||q[j].b==i)continue;

                 int x=find(q[j].a),y=find(q[j].b);

                 if(x!=y){

                     fa[x]=y;

                     num[x]=((num[q[j].b]+q[j].c-num[q[j].a])%+)%;

                 }

                 else{

                     if((num[q[j].b]+q[j].c)%!=num[q[j].a]){wa[i]=j;break;}

                 }

             }

         }

         int cnt=,ans1,ans2=;

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

             if(wa[i]==-){

                 cnt++;

                 ans1=i;

             }

             if(wa[i]>ans2)ans2=wa[i];

         }

         if(!cnt)printf("Impossible\n");

         else if(cnt>)printf("Can not determine\n");

         else printf("Player %d can be determined to be the judge after %d lines\n",ans1,ans2);

     }

     return ;

 }

巴特西

poj2912 带权并查集

最新文章

热门文章