Rochambeau POJ - 2912

佚名 4年前 (2020-07-17) 算法 730人围观抢沙发百度已收录

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

思路：如果x是judge,则除去与x有关的判断，其他判断应该没有冲突。
那么我们需要枚举x是judge的情况下，其他判断还有没有冲突，有冲突就可以说明不是judge。
①judge个数为0，这是不可能的情况
②judge个数大于1，说明没法确定
③judge个数为1，因为一个冲突就能确定某个编号的人是不是judge，
所以我们需要找到在判断冲突时，最迟发生冲突的人是在第几个判断发生冲突。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <vector>
  6 
  7 using namespace std;
  8 
  9 #define ll long long
 10 #define pb push_back
 11 #define fi first
 12 #define se second
 13 
 14 const int N = 510;
 15 struct node
 16 {
 17     int rt, v;
 18 }Fa[N];
 19 struct info
 20 {
 21     int x, y, d;
 22 };
 23 vector<info > Info;
 24 int vis[N * 6];
 25 int n, m;
 26 
 27 inline void init()
 28 {
 29     for(int i = 0; i <= n; ++i){
 30         Fa[i].rt = i;
 31         Fa[i].v = 0;
 32     }
 33 }
 34 
 35 int Find(int x)
 36 {
 37     if(Fa[x].rt == x) return x;
 38     else{
 39         int fax = Fa[x].rt;
 40         Fa[x].rt = Find(fax);
 41         Fa[x].v = (Fa[x].v + Fa[fax].v) % 3;
 42         return Fa[x].rt;
 43     }
 44 }
 45 
 46 bool Union(int x, int y, int d)
 47 {
 48     int fax = Find(x);
 49     int fay = Find(y);
 50     if(fax != fay){
 51         Fa[fay].rt = fax;
 52         Fa[fay].v = (Fa[x].v + d - Fa[y].v + 3) % 3;
 53         return true;
 54     }else{
 55         if(0 == (Fa[x].v + d - Fa[y].v + 3) % 3) return true;
 56         else return false;
 57     }
 58 }
 59 
 60 void solve()
 61 {
 62     while(~scanf("%d%d", &n, &m)){
 63         for(int i = 0; i <= m; ++i) vis[i] = false;
 64         Info.clear();
 65         int x, y, d;
 66         char op;
 67         for(int i = 1; i <= m; ++i){
 68             scanf("%d%c%d", &x, &op, &y);
 69             if(op == '=') d = 0;
 70             else if(op == '>') d = 1;
 71             else d = 2;
 72             Info.pb({x, y, d});
 73         }
 74 
 75         int Judge = 0;
 76         int Cnt = 0;
 77         for(int i = 0; i < n; ++i){
 78             init();
 79             int Conflict = 0;
 80             for(int j = 0; j < m; ++j){
 81                 if(Info[j].x == i || Info[j].y == i) continue;
 82                 if(!Union(Info[j].x, Info[j].y, Info[j].d)){
 83                     Conflict = 1;
 84                     vis[j] = true;
 85                     break;
 86                 }
 87             }
 88             if(!Conflict) Cnt++, Judge = i;
 89         }
 90 
 91         if(!Cnt) puts("Impossible");
 92         else if(Cnt > 1) puts("Can not determine");
 93         else{
 94             int Inx = -1;
 95             for(int i = m - 1; i >= 0; --i){
 96                 if(!vis[i]) continue;
 97                 Inx = i; 
 98                 break;
 99             }
100             printf("Player %d can be determined to be the judge after %d lines\n", Judge, Inx + 1);
101         }
102     }
103 }
104 
105 int main()
106 {
107     solve();
108 
109     return 0;
110 }