poj 3678 Katu Puzzle (2-sat)
Katu PuzzleTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 7010 Accepted: 2573
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.Source
POJ Founder Monthly Contest – 2008.07.27, Dagger思路：
每个X要么是0，要么是1，很明显的2-sat模型，建好图之后直接用模板就行了。
根据这些结论建图：
AND 结果为1，则a、b！=0，结果为0，则a、b最多有一个为1；
OR 结果为1，则a、b至少有一个为1，结果为0，则a、b！=1；
XOR 结果为1，则a、b有且仅有一个为0，结果为0，则a、b全0或全1。
代码:
#include <cstdio>#include <cstring>#define maxn 2005#define MAXN 4000005using namespace std;int n,m,num,flag;int head[maxn];int scc[maxn];int vis[maxn];int stack1[maxn];int stack2[maxn];struct edge{ int v,next;}g[MAXN];void init(){ memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); memset(scc,0,sizeof(scc)); stack1[0] = stack2[0] = num = 0; flag = 1;}void addedge(int u,int v){ num++; g[num].v = v; g[num].next = head[u]; head[u] = num;}void dfs(int cur,int &sig,int &cnt){ if(!flag) return; vis[cur] = ++sig; stack1[++stack1[0]] = cur; stack2[++stack2[0]] = cur; for(int i = head[cur];i;i = g[i].next) { if(!vis[g[i].v]) dfs(g[i].v,sig,cnt); else { if(!scc[g[i].v]) { while(vis[stack2[stack2[0]]] > vis[g[i].v]) stack2[0] --; } } } if(stack2[stack2[0]] == cur) { stack2[0] --; ++cnt; do { scc[stack1[stack1[0]]] = cnt; int tmp = stack1[stack1[0]]; if((tmp >= n && scc[tmp - n] == cnt) || (tmp < n && scc[tmp + n] == cnt)) { flag = false; return; } }while(stack1[stack1[0] --] != cur); }}void Twosat(){ int i,sig,cnt; sig = cnt = 0; for(i=0;i<n+n&&flag;i++) { if(!vis[i]) dfs(i,sig,cnt); }}int main(){ int i,j,a,b,c; char s[10]; while(~scanf("%d%d",&n,&m)) { init(); num=0; for(i=0;i<m;i++) { scanf("%d%d%d%s",&a,&b,&c,s); if(s[0]=='A') { if(c) { addedge(a,a+n); addedge(b,b+n); } else { addedge(a+n,b); addedge(b+n,a); } } else if(s[0]=='O') { if(c) { addedge(a,b+n); addedge(b,a+n); } else { addedge(a+n,a); addedge(b+n,b); } } else { if(c) { addedge(a,b+n); addedge(b+n,a); addedge(b,a+n); addedge(a+n,b); } else { addedge(a,b); addedge(b,a); addedge(a+n,b+n); addedge(b+n,a+n); } } } Twosat(); if(flag) printf("YES\n"); else printf("NO\n"); } return 0;}