【题意】：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, false, sizeof(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