7/21 图论 P4
2-sat
解决布尔可满足性问题。
有多个布尔变量，每个的取值可能为 true 或 false。
有多个形如 (not) x and/or/xor (not)y = true/false 的公式。
问是否存在一组变量取值，可以使所以公式均成立。
考虑更高效地利用题目中的公式进行 “剪枝”。
例如在 x xor not y = true 中，可以在确定 x 和 y 任意一个值的情况下确定另一个唯一值。
每条公式给出了其中变量的限制条件。x and not y = true 中 x 只能取 true，$y$ 只能取 false。
若存在一个元素 $x$，从 x_0 可以走到 $x_1$，从 x_1 可以走到 x_0 则无解。
建图优化
不记了，困。
超级源点、超级终点
例：有一张无向图，给定 s 个起点，$t$ 个终点，求每个起点到每个终点最短路的最小值。
建立一个虚点连接所有起点，建立一个虚点连接所有终点，求两虚点之间最短路。