题目链接：http://poj.org/problem?id=2912
这道题让我略显纠结了，因为要找哪个是裁判，我YY了好几种想法，但是最终结果都是一个混乱，不过最终找到了这个解法。。
其中有一个是裁判的话，那么这个裁判的存在一定会导致这里面的关系出现混乱，因为弱国没有裁判，那么三组人非常和谐，因为他们三组人出的东西都是一样一样的，而裁判出的东西是非常随意的，一会儿这个一会儿那个，所以如果裁判在这个组中，那么最终结果一定会出现矛盾。
看一看时间复杂度，貌似不是那么可怕，可以接受，那么就可以挨个儿的从组内排除，如果一直没有出现矛盾，那么那个人就是应该被排除的，也就是裁判。
当然，那个不可能和无法决定着实让我小蒙圈了一下，但是后来反应过来了，没有裁判是不可能的，裁判有很多个的话就是无法决定的
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 505
9 #define M 2010
10 #define max(a, b) a > b ? a : b
11 struct parent
12 {
13 int p, r;
14 }p[N];
15 int find(int x)
16 {
17 int temp;
18 if (x != p[x].p)
19 {
20 temp = p[x].p;
21 p[x].p = find(temp);
22 p[x].r = (p[temp].r + p[x].r) % 3;
23 }
24 return p[x].p;
25 }
26 int main()
27 {
28 int x[M], y[M], d[M];
29 int r1, r2;
30 int n, m;
31 bool ju;
32 int cnt, ansi, ansn, t;
33 char c;
34 while (scanf("%d%d", &n, &m) != EOF)
35 {
36 for (int i = 0; i < m; i++)
37 {
38 scanf("%d%c%d", &x[i], &c, &y[i]);
39 if (c == '=') d[i] = 0;
40 if (c == '>') d[i] = 1;
41 if (c == '<') d[i] = 2;
42 }
43 cnt = ansi = ansn = 0;
44 for (int i = 0; i < n; i++)
45 {
46 ju = 1;
47 for (int j = 0; j < n; j++)
48 {
49 p[j].p = j; p[j].r = 0;
50 }
51 for (int j = 0; j < m; j++)
52 {
53 if (x[j] == i || y[j] == i) continue;
54 r1 = find(x[j]); r2 = find(y[j]);
55 if (r1 != r2)
56 {
57 p[r2].p = r1;
58 p[r2].r = (6 + p[x[j]].r - p[y[j]].r - d[j]) % 3;
59 }
60 else if ((p[x[j]].r - p[y[j]].r + 3) % 3 != d[j])
61 {
62 ju = 0;
63 ansi = max(ansi, j + 1);
64 break;
65 }
66 }
67 if (ju)
68 {
69 cnt++;
70 ansn = i;
71 if (cnt > 1) break;
72 }
73 }
74 if (cnt == 0) printf("Impossible\n");
75 if (cnt == 1) printf("Player %d can be determined to be the judge after %d lines\n", ansn, ansi);
76 if (cnt > 1) printf("Can not determine\n");
77 }
78 return 0;
79