POJ 2192

WA到要命的题目，最后发现原来是determine多个d 
这个题目很象食物链那道经典题目，不过比那道难些。同样查并中有些变化，RK维护当前节点与根节点的关系。Find的时候注意更新。这题的主要难点是确定最少能通过多少次就能得出裁判。首先存储输入，然后枚举每一个人，枚举每一个人的时候遇到包含此人参加的round都排除，因为此人乱出的。建立查并集，如果发现不满足的关系，则此人不可能为裁判。最后如果可能为裁判的数量不为大于1,说明不能确定谁是裁判。至于所需要的最少round数目，因为k==1,所以所需要大最少round数为枚举时候所能到的最大id号。这点比较难想到。Find使用非递归版本要快得很多。

Problem:		User:
Memory: 684K		Time: 297MS
Language: C++		Result: Accepted

#include <iostream>
using namespace std;
const int MAX=505;
int RK[MAX];
int PR[MAX];
int N,M;
int In[2005][3];
int Step;
int ans;

int Find(int x)
{
    int r=x,sumRK=0,t;
    int sub;
    while(PR[r]!=-1)
    {
        sumRK+=RK[r];
        r=PR[r];
    }
    //路径压缩

    while(x!=r)
    {
        //save

        sub=RK[x];
        t=PR[x];

        PR[x]=r;
        RK[x]=sumRK%3;

        sumRK-=sub;
        x=t;
    }
    return r;
}

bool Union(int a,int b,int Op)//发现错误返回true 否则返回false

{
    int pa=Find(a);
    int pb=Find(b);
    if(pa==pb)
        return (RK[a]+Op)%3 != RK[b];
    //合并

    PR[pa]=pb;
    RK[pa]=RK[b]-(RK[a]+Op);
    while(RK[pa]<0)
        RK[pa]+=3;
    return false;
}

bool Test(int x)
{
    int pa,pb;
    for(int i=0;i<MAX;i++)
    {
        RK[i]=0;
        PR[i]=-1;
    }
    for(int i=0;i<M;i++)
    {
        if(In[i][0]==x||In[i][1]==x)
            continue;
        if(Union(In[i][0],In[i][1],In[i][2]))
        {
            if(Step<i)
                Step=i;
            return false;
        }
    }
    return true;
}

int main()
{
    int a,b;
    char op;
    while(scanf("%d %d",&N,&M)!=EOF)
    {
        ans=0;
        Step=-1;
        for(int i=0;i<M;i++)
        {
            scanf("%d%c%d",&a,&op,&b);
            In[i][0]=a;In[i][1]=b;
            switch(op)
            {
            case '<':
                In[i][2]=2;
                break;
            case '>':
                In[i][2]=1;
                break;
            case '=':
                In[i][2]=0;
                break;
                
            }
        }
        int k=0;
        for(int i=0;i<N;i++)
        {
            if(Test(i))
            {
                k++;
                ans=i;
            }
        }
        if(k==0)
            printf("Impossible\n");
        else if(k==1)
            printf("Player %d can be determined to be the judge after %d lines\n", ans, Step+1);
        else
            printf("Can not determine\n");
    }
    return 0;
}