日记

终于上完政治和历史课了。

课上：生命因何而沉睡？因为我们连着上了 $3$ 节政治课。

太空飞行计划# Link to

我们把每个实验当作一个点权为 $E_i$ 的点，从源点往它建边，容量为 $E_i$，把每个仪器当作点权为 $-I_i$ 的点。从它向汇点建边。容量为 $I_i$。对于每个实验，从它到它所需的仪器建容量为 $\inf$ 的边。那么对于每个实验，选了它就表示源点到它的边满流。对于每个仪器，选了它就表示它到汇点的边没有流量。于是我们就相当于求一个割，它的值为 $val$，而总的利润是 $sum - val$，那么我们要求的就是最小割也就是最大流。

最小路径覆盖# Link to

我们先把每个点都当作一条路径，那么我们就去考虑合并路径。如何合并呢？设第一条路径的结尾是 $u$，第二条路径结尾是 $v$，当且仅当 $u \to v$ 有边的时候才能合并。我们把每个点 $u$ 拆成两个点：出点 $u$ 和入点 $u + n$。对于输入的每条边 $u \to v$，从 $u \to v + n$ 建边，容量为 $1$。再从源点向每个出点建一条容量为 $1$ 的点，从每个入点向汇点建一条容量为 $1$ 的点。这显然是一个二分图。对于其中的一个长度为奇数的匹配路径，它一定是由 $L \to R$ 再从 $R \to L$ 最后再从 $L \to R$ 的。对于每个 $L \to R$，相当于新合并了两条路径。对于每个 $R \to L$，它相当于取消了两条合并。因为是奇数，所以 $L \to R$ 的数量肯定是比 $R \to L$ 的多一条。而一个匹配路径，就相当与网络流上的一条增广路。于是我们求出最大流之后用 $n$ 减掉它就行。

魔术球# Link to

二分一个 $mid$ 出来。把每个 $u,v \in [1,mid]$ 且 $u + v$ 是完全平方数的建一条边，求出这个图的最小路径覆盖。如果大于 $n$ 就 $l = mid - 1$，反之 $r = mid + 1$。

方格取数# Link to

我们按照 $i + j$ 的奇偶性给每个点分类。$i + j \bmod 2 = 1$ 的为白色，其余的是黑色。那么从白色点往四联通的黑色点建边，容量 $\inf$，从源点向白色点建边，从黑色点向汇点建边，容量都是 $1$，那么答案就是所有点的权值和 - 最小割的值。

运输问题和运输问题# Link to 和

最小费用最大流板子。

后日谈 # Link to 后日谈

还是紅蓮華好听啊。