POJ - 2912 Rochambeau (带权并查集+枚举)

题意：有N个人被分为了三组，其中有一个人是开了挂的。同组的人的关系是‘=’，不同组的人关系是‘<’或'>'，但是开了挂的人可以给出自己和他人任意的关系。现在要根据M条关系找出这个开了挂的人。M条关系中可能有多组异常信息。可能会有多个人是外挂，也可能找不出外挂，如果能找到，则要输出其编号X和最早能确定他身份的前Y组条件。

分析：和食物链那题性质很像，但是食物链只需要判断条件对错，而本题是要根据正确性不明的信息找出答案。

还是用模3系的带权并查集解决该问题。枚举每个人i不是外挂的情况，对每一种情况，用不含i的关系去验证，出现矛盾则表示排除了i之外的其他中外挂，记录出现错误的关系编号。

取N-1个人发生验证时发生错误的最大关系编号，就可以推断出谁是外挂了。

如果每个人都不出现错误，则是不可能的情况；如果有多人可以是外挂，则不能找出；否则输出答案。

#include<stdio.h>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

using namespace std;

typedef long long LL;

const int maxn =2e3+;

int fa[maxn],num[maxn];

int pos[maxn];                  //错误发生的编号

void init(int N){

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

        fa[i]=i;

        num[i]=;

    }

}

//模3系

inline int Find(int x){

    if(fa[x]==x) return x;

    int f = fa[x];

    fa[x] = Find(fa[x]);

    num[x] = (num[x]+num[f])%;

    return fa[x];

}

bool Union(int a,int b,int op)

{

    int roota = Find(a),rootb =Find(b);

    if(roota==rootb){

        if((num[a]+op)%!=num[b]) return false;

        else return true;

    }

    fa[rootb] = roota;

    num[rootb] = (-num[b]+num[a]+op+)%;

    return true;

}

struct Query{

    int a,b,op;

}p[maxn];

int main(){

    #ifndef ONLINE_JUDGE

         freopen("in.txt","r",stdin);

         freopen("out.txt","w",stdout);

    #endif

    int N,M,T,Q,u,v,tmp,cas=,a,b;

    char op;

    while(scanf("%d%d",&N,&M) ==  ){

        memset(pos,-,sizeof(pos));

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

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

            if(op=='=') p[i].op=;

            if(op=='<') p[i].op=;

            if(op=='>') p[i].op=;

        }

        for(int i=;i<N;++i){               //尝试枚举每个人不是judge的可能

            init(N);

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

                if(i==p[j].a || i==p[j].b) continue;        //跳过包含i的条件

                if(!Union(p[j].a,p[j].b,p[j].op)) {

                    pos[i]=j;

                    break;                          //找到错误的发生即可推断出judge在i之外的人中

                }

            }

        }

        int cnt=,ans1=,ans2=;

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

            if(pos[i]==-){                     //如果排除这个人不会产生问题，那么他就可以是judge

                cnt++;

                ans1 = i;

            }

            ans2 = max(ans2,pos[i]);            //推断n-1个人不是judge之后，也就知道了谁是judge

        }

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

        else if(cnt==) printf("Impossible\n");

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

    }

    return ;

}