[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 的模板题。

由于数据范围较大,我们考虑用 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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai