POJ 3678 Katu Puzzle（2 - SAT） - from lanshui_Yang
Description
Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ Xi ≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:
Xa op Xb = c
The calculating rules are:
AND01000101OR01001111XOR01001110Given a Katu Puzzle, your task is to determine whether it is solvable.
Input
The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers a (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.
Output
Output a line containing "YES" or "NO".
Sample Input
4 40 1 1 AND1 2 1 OR3 2 0 AND3 0 0 XOR
Sample Output
YES
Hint
X0 = 1, X1 = 1, X2 = 0, X3 = 1. 题目大意：有 n 个变量和m个条件，每个条件格式如下： 给你三个数a ， b ， c 和一个运算字符串op (AND , OR , XOR 等)， 要求Xa op Xb = c 。 问：是否能给每个变量赋值（0 或 1），使得每个条件都能满足？ 解题思路：这道题是一道2 - SAT问题的变形，2 - SAT 问题中是通过条件建立图中的边 ，这道题也类似，也是也要通过条件建立 相应的 边，只不过有些细节需要注意。 请看代码：
#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<vector>#include<cmath>#include<cstdio>#include<queue>#define mem(a , b) memset(a , b , sizeof(a))using namespace std ;const int MAXN = 10000 ;vector<int> G[MAXN * 2] ;bool mark[MAXN * 2] ;int S[MAXN] , c ; // 模拟栈char op[8] ;int n , m ;int pan ; // 判断标志void chu(){ int i ; for(i = 0 ; i < n * 2 ; i ++) G[i].clear() ; mem(mark , 0) ;}void init(){ chu() ; pan = 0 ; int i ; for(i = 0 ; i < m ; i ++) { int a , b , c ; scanf("%d%d%d" , &a , &b , &c) ; scanf("%s" , op) ; if(op[0] == 'A') { if(c == 1) // 注意此时建边的方式 { G[2 * a].push_back(2 * a + 1) ; G[2 * b].push_back(2 * b + 1) ; } else { G[2 * a + 1].push_back(2 * b) ; G[2 * b + 1].push_back(2 * a) ; } } else if(op[0] == 'X') { if(c == 0) { G[2 * a].push_back(2 * b) ; G[2 * a + 1].push_back(2 * b + 1) ; G[2 * b].push_back(2 * a) ; G[2 * b + 1].push_back(2 * a + 1) ; } else { G[2 * a].push_back(2 * b + 1) ; G[2 * a + 1].push_back(2 * b) ; G[2 * b].push_back(2 * a + 1) ; G[2 * b + 1].push_back(2 * a) ; } } else { if(c == 0) // 注意此时建边的方式 { G[2 * a + 1].push_back(2 * a) ; G[2 * b + 1].push_back(2 * b) ; } else { G[2 * a].push_back(2 * b + 1) ; G[2 * b].push_back(2 * a + 1) ; } } }}bool dfs(int x){ if(mark[x ^ 1]) return false ; if(mark[x]) return true ; mark[x] = true ; S[c ++] = x ; int i ; for(i = 0 ; i < G[x].size() ; i ++) { if(!dfs(G[x][i])) return false ; } return true ;}void solve(){ if(pan) puts("NO") ; else { int i ; for(i = 0 ; i < n ; i ++) { if(!mark[i * 2] && !mark[i * 2 + 1]) { c = 0 ; if(!dfs(i * 2)) { while (c > 0) { mark[ S[-- c] ] = false ; } if(!dfs(i * 2 + 1)) { pan = 1 ; break ; } } } } if(pan) puts("NO") ; else puts("YES") ; }}int main(){ while (scanf("%d%d" , &n , &m) != EOF) { init() ; solve() ; } return 0 ;}