【题意】:Alice和Bob要玩n局剪刀石头布, Alice已知Bob在n个回合中每一回合所出的类型(Bob好悲催!OIZ)。现在对于Alice有m个限制,每个限制由a,b,k三个数字来描述。如果k等于0,则代表第a局和第b局Alice必须出的相同。如果k==1,则代表第a局和第b局Alice必须出的不同。求是否存在可以使得Alice每局必胜且符合以上m个要求的方案。 

【题解】:初看像是3-sat的东西,但是3-sat是个NP问题。
               仔细分析,每个回合对于Alice只有两种可能,就是平或者赢,因为Alice要保证不输,所以转化为2-sat问题。

【代码】:
 1 #include "iostream"
 2 #include "cstring"
 3 #include "cstdio"
 4 using namespace std;
 5 #define MAX 10500
 6 #define maxn 20500
 7 #define maxm 10000000
 8 int n, m;
 9 int Bob[MAX], Alice[MAX][2];
10 int dfn[maxn], low[maxn], Dindex, belong[maxn], scc;
11 int s[maxn], top;
12 int eh[maxn], tot;
13 bool instack[maxn];
14 struct Edge {
15     int v, next;
16 }et[maxm];
17 
18 void init() {
19     tot = 0;
20     memset(eh, -1, sizeof(eh));
21 }
22 
23 void addedge(int u, int v) {
24     Edge e = {v, eh[u]};
25     et[tot] = e;
26     eh[u] = tot++;
27 }
28 
29 void dfs(int u) {
30     int v;
31     dfn[u] = low[u] = ++Dindex;
32     s[++top] = u, instack[u] = true;
33     for(int i = eh[u]; i != -1; i = et[i].next) {
34         v = et[i].v;
35         if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
36         else if(instack[v]) low[u] = min(low[u], dfn[v]);
37     }
38     if(dfn[u] == low[u]) {
39         scc++;
40         do {
41             v = s[top--];
42             instack[v] = false;
43             belong[v] = scc;
44         } while(u != v);
45     }
46 }
47 
48 void tarjan() {
49     top = scc = Dindex = 0;
50     memset(dfn, 0, sizeof(dfn));
51     memset(instack, falsesizeof(instack));
52     for(int i = 1; i <= 2 * n; i++)
53         if(!dfn[i]) dfs(i);
54 }
55 
56 bool solvable() {
57     for(int i = 1; i <= n; i++)
58         if(belong[i] == belong[i+n]) return false;
59     return true;
60 }
61 
62 int main() {
63     int T, Case = 1;
64     int a, b, c;
65     scanf("%d", &T);
66     while(T--) {
67         init();
68         scanf("%d%d", &n, &m);
69         for(int i = 1; i <= n; i++) {
70             scanf("%d", &Bob[i]);
71             if(Bob[i] == 1) Alice[i][0] = 1, Alice[i][1] = 2;
72             else if(Bob[i] == 2) Alice[i][0] = 2, Alice[i][1] = 3;
73             else Alice[i][0] = 3, Alice[i][1] = 1;
74         }
75         for(int i = 0; i < m; i++) {
76             scanf("%d%d%d", &a, &b, &c);
77             if(c) {
78                 if(Alice[a][0] == Alice[b][0]) addedge(a, b + n), addedge(b, a + n);
79                 else if(Alice[a][0] == Alice[b][1]) addedge(a, b), addedge(b + n, a + n);
80                 if(Alice[a][1] == Alice[b][0]) addedge(a + n, b + n), addedge(b, a);
81                 else if(Alice[a][1] == Alice[b][1]) addedge(a + n, b), addedge(b + n, a);
82             } else {
83                 if(Alice[a][0] != Alice[b][0]) addedge(a, b + n), addedge(b, a + n);
84                 if(Alice[a][0] != Alice[b][1]) addedge(a, b), addedge(b + n, a + n);
85                 if(Alice[a][1] != Alice[b][0]) addedge(a + n, b + n) , addedge(b, a);
86                 if(Alice[a][1] != Alice[b][1]) addedge(a + n, b), addedge(b + n, a);
87             }
88         }
89         tarjan();
90         printf("Case #%d: ", Case++);
91         if(solvable()) printf("yes\n");
92         else printf("no\n");
93 
94     }
95     return 0;
96 }
97