题意：给定一些变量告诉你他们之间的表达式包括其中的and or xor 然后让你计算是不是有满足的解。
思路：典型的2—SAT问题，首先我是把所有的逻辑表达式化简成->表示然后再a->b之间建立一条边。接着套模版就OK了。
代码如下：
1 //2014-01-21-14.47 2 //2-SAT 3 #include <iostream> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cmath> 7 #include <cstring> 8 #include <algorithm> 9 #include <queue> 10 #include <stack> 11 #include <vector> 12 #define MP(a, b) make_pair(a, b) 13 #define PB(a) push_back(a) 14 15 using namespace std; 16 17 typedef long long ll; 18 typedef pair<int ,int> pii; 19 typedef pair<unsigned int, unsigned int> puu; 20 typedef pair<int ,double> pid; 21 typedef pair<ll, int> pli; 22 23 const int INF = 0x3f3f3f3f; 24 const double eps = 1e-6; 25 const int LEN = 1010; 26 vector<int> Map[LEN]; 27 bool mark[LEN*2]; 28 int S[LEN*2], c; 29 30 bool dfs(int x) { 31 if(mark[x^1]) return false; 32 if(mark[x]) return true; 33 mark[x] = true; 34 S[c++] = x; 35 for(int i=0; i<Map[x].size(); i++) 36 if(!dfs(Map[x][i])) return false; 37 return true; 38 } 39 40 void init(int n){ 41 for(int i=0; i<n*2; i++)Map[i].clear(); 42 memset(mark, 0, sizeof mark); 43 } 44 45 void add_clause(int x, int xval, int y, int yval) 46 { 47 x = x*2 + xval; 48 y = y*2 + yval; 49 Map[x].PB(y); 50 } 51 52 bool solve(int n){ 53 for(int i=0; i<n*2; i+=2) 54 if(!mark[i] && !mark[i+1]){ 55 c = 0; 56 if(!dfs(i)) { 57 while(c > 0) mark[S[--c]] = false; 58 if(!dfs(i+1)) return false; 59 } 60 } 61 return true; 62 } 63 64 int main() 65 { 66 // freopen("in.txt", "r", stdin); 67 68 int n, m, a, b, res; 69 char op[11]; 70 while(scanf("%d%d", &n, &m)!=EOF){ 71 init(n); 72 for(int i=0; i<m; i++){ 73 scanf("%d%d%d%s", &a, &b, &res, op); 74 if(!strcmp(op, "AND") && res) { 75 add_clause(a, 0, a, 1); 76 add_clause(b, 0, b, 1); 77 }else if(!strcmp(op, "AND") && !res){ 78 add_clause(a, 1, b, 0); 79 add_clause(b, 1, a, 0); 80 }else if(!strcmp(op, "XOR") && res){ 81 add_clause(a, 0, b, 1); 82 add_clause(a, 1, b, 0); 83 add_clause(b, 0, a, 1); 84 add_clause(b, 1, a, 0); 85 }else if(!strcmp(op, "XOR") && !res){ 86 add_clause(a, 0, b, 0); 87 add_clause(a, 1, b, 1); 88 add_clause(b, 0, a, 0); 89 add_clause(b, 1, a, 1); 90 }else if(!strcmp(op, "OR") && res){ 91 add_clause(a, 0, b, 1); 92 add_clause(b, 0, a, 1); 93 }else { 94 add_clause(a, 1, a, 0); 95 add_clause(b, 1, b, 0); 96 } 97 } 98 if(solve(n)) printf("YES "); 99 else printf("NO "); 100 } 101 return 0; 102 }