POJ 3678 Katu Puzzle

Katu Puzzle

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 3678
64-bit integer IO format: %lld Java class name: Main

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:

AND	0	1
0	0	0
1	0	1

OR	0	1
0	0	1
1	1	1

XOR	0	1
0	0	1
1	1	0

Given 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 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

Sample Output

YES

Source

POJ Founder Monthly Contest – 2008.07.27

解题：2SAT

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <climits>
  7 #include <vector>
  8 #include <queue>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <set>
 12 #include <stack>
 13 #define LL long long
 14 #define pii pair<int,int>
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 2010;
 18 struct arc{
 19     int to,next;
 20     arc(int x = 0,int y = -1){
 21         to = x;
 22         next = y;
 23     }
 24 };
 25 arc e[4000010];
 26 int head[maxn],dfn[maxn],low[maxn],belong[maxn];
 27 int tot,cnt,scc,n,m;
 28 bool instack[maxn];
 29 stack<int>stk;
 30 void add(int u,int v){
 31     e[tot] = arc(v,head[u]);
 32     head[u] = tot++;
 33 }
 34 void init(){
 35     for(int i = 0; i < maxn; i++){
 36         belong[i] = 0;
 37         low[i] = dfn[i] = 0;
 38         head[i] = -1;
 39         instack[i] = false;
 40     }
 41     while(!stk.empty()) stk.pop();
 42     tot = cnt = scc = 0;
 43 }
 44 void tarjan(int u){
 45     dfn[u] = low[u] = ++cnt;
 46     instack[u] = true;
 47     stk.push(u);
 48     for(int i = head[u]; ~i; i = e[i].next){
 49         if(!dfn[e[i].to]){
 50             tarjan(e[i].to);
 51             if(low[e[i].to] < low[u]) low[u] = low[e[i].to];
 52         }else if(instack[e[i].to] && dfn[e[i].to] < low[u])
 53             low[u] = dfn[e[i].to];
 54     }
 55     if(dfn[u] == low[u]){
 56         scc++;
 57         int v;
 58         do{
 59             v = stk.top();
 60             stk.pop();
 61             instack[v] = false;
 62             belong[v] = scc;
 63         }while(v != u);
 64     }
 65 }
 66 bool solve(){
 67     for(int i = 0; i < (n<<1); i++)
 68         if(!dfn[i]) tarjan(i);
 69     for(int i = 0; i < n; i++)
 70         if(belong[i] == belong[i+n]) return false;
 71     return true;
 72 }
 73 int main() {
 74     char op[5];
 75     int u,v,c;
 76     while(~scanf("%d %d",&n,&m)){
 77         init();
 78         while(m--){
 79             scanf("%d %d %d %s",&u,&v,&c,op);
 80             if(op[0] == 'A'){
 81                 if(c){
 82                     add(u+n,v+n);
 83                     add(v+n,u+n);
 84                     add(u,u+n);
 85                     add(v,v+n);
 86                 }else{
 87                     add(u+n,v);
 88                     add(v+n,u);
 89                 }
 90             }else if(op[0] == 'O'){
 91                 if(c){
 92                     add(u,v+n);
 93                     add(v,u+n);
 94                 }else{
 95                     add(u,v);
 96                     add(v,u);
 97                     add(u+n,u);
 98                     add(v+n,v);
 99                 }
100             }else if(op[0] == 'X'){
101                 if(c){
102                     add(u,v+n);
103                     add(v,u+n);
104                     add(u+n,v);
105                     add(v+n,u);
106                 }else{
107                     add(u,v);
108                     add(v,u);
109                     add(u+n,v+n);
110                     add(v+n,u+n);
111                 }
112             }
113         }
114         printf("%s
",solve()?"YES":"NO");
115     }
116     return 0;
117 }

View Code