[POJ 3678] Katu Puzzle【2-SAT】
Problem:
| Time Limit: 1000MS | Memory Limit: 65536K |
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:
|
|
|
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
Hint
Source
Solution:
2-SAT 的模板题。
由于数据范围较大，我们考虑用 Tarjan 缩点。
若缩点后任意一对点（指表示同一个布尔值的 0, 1 取值）在同一强连通分量中，则出现矛盾，不存在解；否则一定存在解。
注意顶点编号从 0 开始，若栈的初始值设为 0 则会导致出栈判断失误，可能得到错误答案。
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'){
if(c) G.addedge(a ^ 1, a), G.addedge(b ^ 1, b);
else G.addedge(a, b ^ 1), G.addedge(b, a ^ 1);
}
else if(op[0] == 'O'){
if(c) G.addedge(a ^ 1, b), G.addedge(b ^ 1, a);
else G.addedge(a, a ^ 1), G.addedge(b, b ^ 1);
}
else{
if(c) G.addedge(a, b ^ 1), G.addedge(a ^ 1, b), G.addedge(b, a ^ 1), G.addedge(b ^ 1, a);
else G.addedge(a, b), G.addedge(a ^ 1, b ^ 1), G.addedge(b, a), G.addedge(b ^ 1, a ^ 1);
}
}
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;
}
发表评论