POJ 3678 Katu Puzzle（2-SAT）

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 V_i a value X_i (0 ≤ X_i≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:

X_a op X_b = 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"

题目大意：每条边给出一个OP和一个ANS，要求每条边的连点A、B，符合A OP B == ANS，其中A、B、ANS都为0或1

思路：2-SAT问题

A AND B == 0则A真→B假，B真→A假

A AND B == 1则A、B都为真，即B假→B真，A假→A真（即不能出现A假推出A真的情况，A假不能被选上，在强连通图中，若A真通过多步推出A假，即成环，无解）

A OR B == 0则A、B都为假，即B真→B假，A真→A假（同上）

A OR B == 1则A假→B真，B假→A真

A XOR B == 0则A真↔B真，A假↔B假

A XOR B == 1则A真↔B假，A假↔B真

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int MAXN = 2010;
 6 const int MAXM = 1000010*4;
 7 
 8 struct TwoSAT{
 9     int n, ecnt, dfs_clock, scc_cnt;
10     int St[MAXN], c;
11     int head[MAXN], sccno[MAXN], lowlink[MAXN], pre[MAXN];
12     int next[MAXM], to[MAXM];
13 
14     void init(int nn){
15         n = nn;
16         ecnt = 2; dfs_clock = scc_cnt = 0;
17         memset(head,0,sizeof(head));
18     }
19 
20     void addEdge(int x, int y){
21         to[ecnt] = y; next[ecnt] = head[x]; head[x] = ecnt++;
22     }
23 
24     void addEdge2(int x, int y){
25         addEdge(x,y); addEdge(y,x);
26     }
27 
28     void dfs(int u){
29         lowlink[u] = pre[u] = ++dfs_clock;
30         St[++c] = u;
31         for(int p = head[u]; p; p = next[p]){
32             int &v = to[p];
33             if(!pre[v]){
34                 dfs(v);
35                 if(lowlink[u] > lowlink[v]) lowlink[u] = lowlink[v];
36             }else if(!sccno[v]){
37                 if(lowlink[u] > pre[v]) lowlink[u] = pre[v];
38             }
39         }
40         if(lowlink[u] == pre[u]){
41             ++scc_cnt;
42             while(true){
43                 int x = St[c--];
44                 sccno[x] = scc_cnt;
45                 if(x == u) break;
46             }
47         }
48     }
49 
50     bool solve(){
51         for(int i = 0; i < n; ++i)
52             if(!pre[i]) dfs(i);
53         for(int i = 0; i < n; i += 2)
54             if(sccno[i] == sccno[i^1]) return false;
55         return true;
56     }
57 
58 } G;
59 
60 int main(){
61     int n, m, a, b, c;
62     char d[5];
63     while(scanf("%d%d",&n,&m)!=EOF){
64         G.init(2*n);
65         while(m--){
66             scanf("%d%d%d%s",&a,&b,&c,d);
67             if(d[0] == 'A' && c == 0){//a&b=false
68                 G.addEdge(a*2, b*2+1);
69                 G.addEdge(b*2, a*2+1);
70             }
71             if(d[0] == 'A' && c == 1){//a&b=true
72                 G.addEdge(a*2+1, a*2);
73                 G.addEdge(b*2+1, b*2);
74             }
75             if(d[0] == 'O' && c == 0){//a|b=false
76                 G.addEdge(a*2, a*2+1);
77                 G.addEdge(b*2, b*2+1);
78             }
79             if(d[0] == 'O' && c == 1){//a|b=true
80                 G.addEdge(b*2+1, a*2);
81                 G.addEdge(a*2+1, b*2);
82             }
83             if(d[0] == 'X' && c == 0){//a^b=false
84                 G.addEdge2(a*2, b*2);
85                 G.addEdge2(a*2+1, b*2+1);
86             }
87             if(d[0] == 'X' && c == 1){//a^b=true
88                 G.addEdge2(a*2, b*2+1);
89                 G.addEdge2(a*2+1, b*2);
90             }
91         }
92         if(G.solve()) printf("YES
");
93         else printf("NO
");
94     }
95     return 0;
96 }

141MS