重点是怎么建图，纠结了一天看2-SAT的资料...
a 表示1， a'表示0，则：
1、a and b = 1, a' -> a, b'-> b （a b 同时为1 ）
2、a and b = 0, a -> b', b -> a' (a b 不同时为1)
3、a or b = 1, a' -> b, b' -> a （a b不同时为0）
4、a or b = 0, a -> a', b -> b' （a b同时为0 同1）
5、a xor b = 1, a -> b', b -> a', a' -> b, b' -> a (a b 不相等)
6、a xor b = 0, a -> b, b -> a, a' -> b', b' -> a' （a b 相等）
以1为例：a ^ b = (a V a) ^ (b V b) 因为 A V B 建图为 ~A -> B, ~B -> A， 这里把B换成A就是 ～A -> A,同理， ～B -> B
另一个关于a and b = 1, a' -> a, b'-> b 的解释：
渣代码：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 const int N = 2005; 10 const int M = 1000005; 11 12 struct node { 13 int next; 14 int to; 15 } g[M]; 16 17 int head[N], scc[N]; 18 int dfn[N], low[N]; 19 int t, cnt, ind; 20 bool vis[N]; 21 22 stack s; 23 24 void init() { 25 for(int i = 0; i < N; i++) { 26 head[i] = scc[i] = dfn[i] = low[i] = vis[i] = 0; 27 } 28 t = 1; ind = cnt = 0; 29 } 30 31 void add(int u, int v) { 32 g[t].to = v; g[t].next = head[u]; head[u] = t++; 33 } 34 35 void tarjan(int u) { 36 int v, i; 37 dfn[u] = low[u] = ++ind; 38 vis[u] = true; s.push(u); 39 for(i = head[u]; i; i = g[i].next) { 40 v = g[i].to; 41 if(!dfn[v]) { 42 tarjan(v); 43 low[u] = min(low[u], low[v]); 44 } else if(vis[v]) { 45 low[u] = min(low[u], dfn[v]); 46 } 47 } 48 if(low[u] == dfn[u]) { 49 cnt++; 50 do { 51 v = s.top(); s.pop(); 52 scc[v] = cnt; 53 vis[v] = false; 54 } while(v != u); 55 } 56 } 57 58 int main() { 59 //freopen("data.in", "r", stdin); 60 61 int n, m, i; 62 int a, b, c; 63 bool flag; 64 string str; 65 while(~scanf("%d%d", &n, &m)) { 66 init(); 67 while(m--) { 68 cin >> a >> b >> c >> str; 69 //cout << a << " " << b << " " << c << " " << str << endl; 70 if(str == "AND") { 71 if(c) {add(a, a + n); add(b, b + n);} 72 else {add(a + n, b); add(b + n, a);} 73 } else if(str == "OR") { 74 if(c) {add(a, b + n); add(b, a + n);} 75 else {add(a + n, a); add(b + n, b);} 76 } else if(str == "XOR") { 77 if(c) {add(a + n, b); add(a, b + n); add(b, a + n); add(b + n, a);} 78 else {add(a, b); add(b, a); add(a + n, b + n); add(b + n, a + n);} 79 } 80 } 81 for(i = 0; i < 2*n; i++) { 82 if(!dfn[i]) tarjan(i); 83 } 84 for(flag = true, i = 0; i < n; i++) { 85 if(scc[i] == scc[i + n]) { 86 cout << "NO" << endl; 87 flag = false; break; 88 } 89 } 90 if(flag) cout << "YES" << endl; 91 } 92 return 0; 93 }