[POJ2912]Rochambeau（并查集）

传送门

题意：

n个人分成三组，玩石头剪子布游戏，同一组的人只能出同样固定的的手势，其中有一个是裁判不属于任何组，可以出任意手势，给出m个信息x op y 表示x,y是从三个组里面随机抽取的或者是裁判，他们之间的输赢关系。让你判断最少在第几组信息时，可以唯一判断出裁判，并将裁判号，以及在第几组后判断出来的输出。

思路：
注意这里是能够唯一确定，也就是存在确定的唯一一个裁判。那么我们可以从n个人里面枚举裁判，然后判断除去裁判之后是否还存在矛盾的关系（存在矛盾肯定是裁判在其中导致的），如果存在那么排除该人，记录在第几个信息出现的。枚举完后，如果只存在一个矛盾的人那么这个人就是裁判，如果不存在矛盾，输出Impossible，否则就表示存在多个裁判，输出Can not determine 这里存在矛盾的判断就是用分类并查集处理的了。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #define N 1000001 4 #define max(x, y) ((x) > (y) ? (x) : (y)) 5 6 int n, m, k, ans, cnt; 7 int a[N], b[N], f[N], d[N], err[N]; 8 char s[N]; 9 10 inline int find(int x) 11 18 return f[x]; 19 } 20 21 int main() 22 43 if(s[j] == '<' && (d[a[j]] d[b[j]] + 3) % 3 != 1 && (d[b[j]] d[a[j]] + 3) % 3 != 2) 44 48 if(s[j] == '>' && (d[a[j]] d[b[j]] + 3) % 3 != 2 && (d[b[j]] d[a[j]] + 3) % 3 != 1) 49 53 } 54 else 55 61 if(s[j] == '<') 62 66 if(s[j] == '>') 67 71 } 72 } 73 } 74 k = ans = cnt = 0; 75 for(i = 0; i < n; i++) 76 82 ans = max(ans, err[i]); 83 } 84 if (cnt == 0) puts("Impossible"); 85 else if (cnt == 1) printf("Player %d can be determined to be the judge after %d lines\n", k, ans); 86 else puts("Can not determine"); 87 } 88 }
View Code

上一篇：[POJ2406]Power Strings

下一篇：[CODEVS1915] 分配问题（最小费用最大流）

---

并查集