有 n 个布尔变量 x_1 \sim x_n,另有 m 个需要满足的条件,每个条件的形式都是 「x_i 为 true
/ false
或 x_j 为 true
/ false
」。比如 「x_1 为真或 x_3 为假」、「x_7 为假或 x_2 为假」。
2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。
第一行两个整数 n 和 m,意义如题面所述。
接下来 m 行每行 4 个整数 i, a, j, b,表示 「x_i 为 a 或 x_j 为 b」(a, b\in {0,1})
如无解,输出 IMPOSSIBLE
;否则输出 POSSIBLE
。
下一行 n 个整数 x_1\sim x_n(x_i\in{0,1}),表示构造出的解。
3 1 1 1 3 0
POSSIBLE 0 0 0
1\leq n, m\leq 5×10^5 。
模板