【題意】：有n個變量，每個可以取0或者1，再給出m組關系，每組關系都是兩個變量進行運算可以得到的結果，運算有AND OR XOR三種，問能否根據這些關系，判斷每個變量的取值。
【題解】：比較明顯的2-Sat問題，關鍵是要把所有情況考慮完全。用x表示該變量取0，x’表示取1，下面說下如何構圖:
a and b == 1, 這種情況a和b必須取1，所以連邊a->a', b->b'.
a and b == 0, 這種情況a和b不能同時為1，所以連邊a'->b, b'->a.
a or b == 1, 這種情況a和b不能同時為0，所以連邊a->b', b->a'.
a or b == 0, 這種情況a和b必須同時為0，所以連邊a'->a, b'->b.
a xor b == 1, 這種情況a和b取值要相反，所以連邊a->b', a'->b, b->a', b'->a.
a xor b == 0, 這種情況a和b取值要相同，所以連邊a->b, b->a, a'->b', b'->a'.
構圖后強連通縮點判斷有無解即可。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 2500
6 #define maxm 5000000
7 int n, m;
8 int eh[maxn], tot;
9 int belong[maxn], scc, dfn[maxn], low[maxn], Dindex;
10 int s[maxn], top;
11 bool instack[maxn];
12 struct Edge {
13 int v, next;
14 }et[maxm];
15
16 void init() {
17 tot = 0;
18 memset(eh, -1, sizeof(eh));
19 }
20
21 void addedge(int u, int v) {
22 Edge e = {v, eh[u]};
23 et[tot] = e;
24 eh[u] = tot++;
25 }
26
27 void dfs(int u) {
28 int v;
29 dfn[u] = low[u] = ++Dindex;
30 s[++top] = u, instack[u] = true;
31 for(int i = eh[u]; i != -1; i = et[i].next) {
32 v = et[i].v;
33 if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
34 else if(instack[v]) low[u] = min(low[u], dfn[v]);
35 }
36 if(dfn[u] == low[u]) {
37 scc++;
38 do {
39 v = s[top--];
40 instack[v] = false;
41 belong[v] = scc;
42 }while(v != u);
43 }
44 }
45
46 void tarjan() {
47 top = scc = Dindex = 0;
48 memset(instack, false, sizeof(instack));
49 memset(dfn, 0, sizeof(dfn));
50 for(int i = 0; i < 2 * n; i++)
51 if(!dfn[i]) dfs(i);
52 }
53
54 bool solvable() {
55 for(int i = 0; i < 2 * n; i += 2)
56 if(belong[i] == belong[i^1]) return false;
57 return true;
58 }
59
60 void build(int u, int v, int c, char *s) {
61 int a = 2 * u, b = 2 * v;
62 if(strcmp(s, "AND") == 0) {
63 if(c) addedge(a, a^1), addedge(b, b^1);
64 else addedge(a^1, b), addedge(b^1, a);
65 } else if(strcmp(s, "OR") == 0) {
66 if(c) addedge(a, b^1), addedge(b, a^1);
67 else addedge(a^1, a), addedge(b^1, b);
68 } else {
69 if(c) addedge(a, b^1), addedge(b, a^1), addedge(a^1, b), addedge(b^1, a);
70 else addedge(a, b), addedge(a^1, b^1), addedge(b, a), addedge(b^1, a^1);
71 }
72 }
73
74 int main() {
75 char s[5];
76 int u, v, c;
77 while(~scanf("%d%d", &n, &m)) {
78 init();
79 for(int i = 0; i < m; i++) {
80 scanf("%d%d%d%s", &u, &v, &c, s);
81 build(u, v, c, s);
82 }
83 tarjan();
84 if(solvable()) printf("YES\n");
85 else printf("NO\n");
86 break;
87 }
88 return 0;
89 }