poj 2912 Rochambeau

点击打开链接poj 2912

思路: 带权并查集
分析:
1 有n个小孩玩游戏，里面有一个入是裁判，剩下的人分为三组。现在我们既不知道裁判是谁也不知道分组的情况。现在n个小孩玩剪刀石头布，已知每组的小孩只会出同一种手势，问谁是裁判
2 题目说了输入=的时候说明是同一组，如果是<或>的时候说明是不同一组，那么根据食物链那一题的思路，我们设rank[x]表示x和根节点的关系，如果是=那么rank[x] = 0，如果是<则rank[x] = 1,否则为rank[x] = 2
3 剩下的就是怎么求最少几轮得到裁判的编号，要得出最后的裁判，也就是其他的人度不满足的最大的那一轮，因为那一轮过后就能确定裁判了

4 判断关系的时候，如果是不同的集合那就合并，否则判断是否有rank[x] == (rank[y]+val)%3

5 注意输入数据可能会有空格

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 510;

struct Node{
    int x;
    int y;
    int val;
};
Node node[4*MAXN];

int n , m;
int father[MAXN];
int rank[MAXN];

void init(int n){
    memset(rank , 0 , sizeof(rank));
    for(int i = 0 ; i < n ; i++)
       father[i] = i;
}

int find(int x){
    if(father[x] != x){
        int fa = father[x];
        father[x] = find(fa);
        rank[x] = (rank[fa]+rank[x])%3;
    }
    return father[x];
}

void solve(){
    int ans , step;
    ans = -1;
    step = 0;
    for(int i = 0 ; i < n ; i++){
       init(n); 
       int tmpStep = 0;
       int j;
       for(j = 0 ; j < m ; j++){
           int x = node[j].x;   
           int y = node[j].y;   
           int fx = find(x);
           int fy = find(y);
           if(x == i || y == i)
               continue;
           if(fx != fy){
               father[fx] = fy;
               rank[fx] = (rank[y]+node[j].val-rank[x]+3)%3;
           }
           else{
               if(rank[x] != (rank[y]+node[j].val)%3){
                   tmpStep = j+1;
                   break;
               }
           }
       }      
       if(j == m){
           if(ans == -1)
               ans = i;
           else{
               puts("Can not determine");
               return;
           }
       }
       else
           step = max(tmpStep , step);
    }
    if(ans == -1)
        puts("Impossible");
    else
        printf("Player %d can be determined to be the judge after %d lines\n" , ans , step);
}

int main(){
    char ch;
    while(scanf("%d%d" , &n , &m) != EOF){
        for(int i = 0 ; i < m ; i++){
            scanf("%d" , &node[i].x);
            while((ch = getchar()) == ' ');
            scanf("%d" , &node[i].y);
            if(ch == '=')
                node[i].val = 0;
            else if(ch == '<')
                node[i].val = 1;
            else 
                node[i].val = 2;
        }
        solve();
    }
    return 0;
}