关于 POJ 3678]卡图难题的近10条评论(全部评论)
2-SAT打卡 ┭┮﹏┭┮ 2023-10-19 17:18 2楼
我明明是来做水题的，为什么这题是零星锝镆氪锂铽 2022-06-16 22:05 1楼

3452. POJ 3678]卡图难题

★★★☆ 输入文件：katu.in 输出文件：katu.out 简单对比
时间限制：1 s 内存限制：256 MiB

有 $n$ 个变量 $x_0\sim x_{n-1}$，每个变量的可能取值为 $0$ 或 $1$。

给定 $m$ 个算式，每个算式形如 $x_a\ op\ x_b=c$，其中 $a,b$ 是变量编号，$c$ 是数字 $0$ 或 $1$，$op$ 是 AND,OR,XOR 三个位运算之一。

求是否存在对每个变量的合法赋值，使所有算式都成立。

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含三个整数 $a,b,c$，以及一个位运算（AND,OR,XOR 中的一个）。

输出结果，如果存在，输出 YES，否则输出 NO。

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

YES

$1\leq n\leq 1000,1\leq m\leq 10^6$