标签: 2-SAT

2 篇文章

LuoguP3209 [HNOI2010] 平面图判定
Description 判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图是否是平面图,图中存在一个包含所有顶点的环,即存在哈密顿回路。 对于一个无向图 $G=(V,E)$,如果能够做到把它画在同一个平面上,使得 $\forall (a,b)(c,d)$,$a,b,c,d$ 两两不等的情况下,边 $(a,b)$ 和…
LuoguP3007 [USACO11JAN] The Continental Cowngress G
Description 给出 $n$ 个法案,$m$ 头牛的意见, 每头牛会表决两次。每次表决格式为 i Y 表示“支持 $i$ 号法案”或 i N 表示“反对 $i$ 号法案”。最终,每头牛至少要有一个表决被满足。不可能成立的话输出 IMPOSSIBLE,否则输出方案。 $1\leq N \leq 1,000,1\leq M \leq 4,000…