3678：Katu Puzzle

题目描述

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.

输入解释

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 a line containing "YES" or "NO".

输入样例

4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

输出样例

YES

提示

X₀ = 1, X₁ = 1, X₂ = 0, X₃ = 1.

该题目是Virtual Judge题目，来自北京大学POJ

题目来源 POJ Founder Monthly Contest – 2008.07.27, Dagger

源链接： POJ-3678

最后修改于 2020-10-29T07:07:59+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
1000	65536