poj 2912 Rochambeau（带权并查集）

poj 2912 Rochambeau（带权并查集）

题目：​​class="data-table" data-id="t7a7e9d1-72Z8fd6l" data-width="" style="outline: none; border-collapse: collapse; width: 100%;">

Time Limit: 5000MS

Memory Limit: 65536K

Total Submissions: 2293

Accepted: 822

Description

N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?

Input

Input contains multiple test cases. Each test case starts with two integers N and M (1 ≤ N ≤ 500, 0 ≤ M ≤ 2,000) in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in [0, N) separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.

Output

There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.

Sample Input

3 3 0<1 1<2 2<0 3 5 0<1 0>1 1<2 1>2 0<2 4 4 0<1 0>1 2<3 2>3 1 0

Sample Output

Can not determine Player 1 can be determined to be the judge after 4 lines Impossible Player 0 can be determined to be the judge after 0 lines

分析：大意是，许多人分成三组一起来玩剪刀石头布，有一个人是judge，可以任意出，相同组的人必须出一样，问哪一个是judge。这需要枚举，并且和食物链那个问题很相似。这里假设一个人是judge，把他排除，如果结果只有一个矛盾那么他就是judge（这个矛盾就是一个0,1,2的循环）；如果有多个矛盾（多个循环，1,2；2,1；0,1；1,0,；0,1,2等）那么他不是judge，无法判断；如果没有一个循环，那是不可能的（Impossible）。

#include #include #include using namespace std;struct Node{ int u,v,k;}a[2005];int n,m;int pre[505],r[505];int error[505];char str[1000];int find(int x){ if(x==pre[x]) return x; int f=pre[x]; pre[x]=find(pre[x]); r[x]=(r[x]+r[f])%3; return pre[x];}int main(){ //freopen("cin.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { getchar(); for(int i=0;i'||str[j]=='<'||str[j]=='='){ tag=j; break; } q1=q1*10+str[j]-'0'; } for(int j=tag+1;j1) puts("Can not determine"); else printf("Player %d can be determined to be the judge after %d lines\n",p1,p2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。