2-SAT
「JSOI2010」满汉全席-2-SAT
· ✏️ 488 words · ☕ 1 mins read

题意过长,概括如下:

你有 $n$ 种食材,评委 $m$ 个要求,你需要加工这 $n$ 种食材,每种从"汉式(h)“或者"满式(m)“中选择一种。每个要求用两个形如 $\text{h} x$ 或者 $\text{m}x$ ( $x$ 为一个 $1 \sim n$ 的正整数),意为第 $x$ 道菜需要用用"汉式(h)“或者"满式(m)“来进行加工,每个要求中的两个条件必须至少满足一个,每种食材最多只能用一种方式来加工。

请你判断存不存在一个合法的方式。


「HNOI2010」平面图判定-2-SAT
· ✏️ 574 words · ☕ 2 mins read

若能将无向图 $G=(V, E)$ 画在平面上使得任意两条无重合顶点的边不相交,则称 $G$ 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图,图中存在一个包含所有顶点的环,即存在哈密顿回路。