[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; }
发表评论