开发者社区云计算文章正文

[POJ3678] Katu Puzzle | 2-SAT 入门

2022-06-14 153

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Description Katu Puzzle is presented as a directed graph G ( V , E ) with each edge e ( a , b ) labeled by a boolean operator op (oneofAND,OR,XOR) and an integer c ( 0 ≤ c ≤ 1 ) . One Katu is solvable if one can find each vertex Vi a value X i ( 0 ≤ X i ≤ 1 )

Description
Katu Puzzle is presented as a directed graph G ( V , E ) with each edge e ( a , b ) labeled by a boolean operator op (oneofAND,OR,XOR) and an integer c ( 0 ≤ c ≤ 1 ) . One Katu is solvable if one can find each vertex Vi 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:
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 ) (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