題目鏈接：http://poj.org/problem?id=2912
這道題讓我略顯糾結(jié)了，因?yàn)橐夷膫€(gè)是裁判，我YY了好幾種想法，但是最終結(jié)果都是一個(gè)混亂，不過最終找到了這個(gè)解法。。
其中有一個(gè)是裁判的話，那么這個(gè)裁判的存在一定會導(dǎo)致這里面的關(guān)系出現(xiàn)混亂，因?yàn)槿鯂鴽]有裁判，那么三組人非常和諧，因?yàn)樗麄內(nèi)M人出的東西都是一樣一樣的，而裁判出的東西是非常隨意的，一會兒這個(gè)一會兒那個(gè)，所以如果裁判在這個(gè)組中，那么最終結(jié)果一定會出現(xiàn)矛盾。
看一看時(shí)間復(fù)雜度，貌似不是那么可怕，可以接受，那么就可以挨個(gè)兒的從組內(nèi)排除，如果一直沒有出現(xiàn)矛盾，那么那個(gè)人就是應(yīng)該被排除的，也就是裁判。
當(dāng)然，那個(gè)不可能和無法決定著實(shí)讓我小蒙圈了一下，但是后來反應(yīng)過來了，沒有裁判是不可能的，裁判有很多個(gè)的話就是無法決定的
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