【题意】：有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 }