# [POJ 3678] Katu Puzzle【2-SAT】

• 2018-01-12
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K

Description

Katu Puzzle is presented as a directed graph G(VE) 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 ≤ X≤ 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 (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`

Hint

X0 = 1, X1 = 1, X2 = 0, X3 = 1.

Source

POJ Founder Monthly Contest – 2008.07.27, Dagger

## Solution:

2-SAT 的模板题。

2-SAT 的建图详见 [HDU 1814] Peaceful Commission【2-SAT】

## Code: O(N+M) [384K, 94MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, M;

struct Edge{
int np;
Edge *nxt;
};

struct Graph{
Edge *V[2002], E[2000002];
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];}
} G;

int dfn[2002], dfstime;
int low[2002];
int Stack[2002], tops;
int Status[2002];
int Color[2002], topc;

inline void Tarjan(int u){
dfn[u] = low[u] = ++dfstime;
Stack[++tops] = u, Status[u] = 1;
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){
if(Status[ne->np] == 0){
Tarjan(ne->np);
low[u] = min(low[u], low[ne->np]);
}
else if(Status[ne->np] == 1) low[u] = min(low[u], dfn[ne->np]);
}
if(low[u] == dfn[u]){
topc++;
while(Stack[tops + 1] != u){
Color[Stack[tops]] = topc;
Status[Stack[tops--]] = -1;
}
}
}

int main(){
while(scanf("%d%d", &N, &M) != EOF){
N <<= 1;
G.clear();
for(register int i = 1; i <= M; i++){
int a, b, c;
char op[5];
scanf("%d%d%d%s", &a, &b, &c, op), a <<= 1, b <<= 1;
if(op[0] == 'A'){
}
else if(op[0] == 'O'){
}
else{
}
}

dfstime = tops = topc = 0;
memset(Status, 0, sizeof(Status));
memset(Stack, -1, sizeof(Stack));
// Beware that the default is equal to the Vertex 0 that causes error on line 43 !!!
for(register int i = 0; i < N; i++)
if(!Status[i]) Tarjan(i);

bool isSolvable = 1;
for(register int i = 0; i < N; i += 2)
if(Color[i] == Color[i ^ 1]){
puts("NO"), isSolvable = 0;
break;
}
if(isSolvable) puts("YES");
// If there's any pair drawn the same color, we're unable to meet all the limits
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai