网络流建模 ​

二分图最大匹配 ​

内容 ​

将边分成匹配和非匹配边，使每个点相邻的匹配边数量 $\leq 1$。

思路 ​

考虑刻画限制数量 $\leq 1$，而最大流是容易刻画数量限制的。利用二分图，分别对左右部点进行处理即可。

即对于二分图 $G=(V = L\cup R, E)$，其中 $L$ 和 $R$ 为左右部点集，可构建源点 $s$ 和汇点 $t$，从 $s$ 向 $L$ 中每个点连容量为 $1$ 的边，从 $R$ 中每个点向 $t$ 连容量为 $1$ 的边，原图中的边容量设为 $1$。通过求 $s$ 到 $t$ 的最大流，可得到二分图的最大匹配。

当然，也可以认为这要转化成刻画选择，可以用最小割，但复杂度更差。

集合划分问题 ​

内容 ​

设有 $n$ 个物品，对于每个物品 $i$，选择 $A$ 有代价 $a_i$，选择 $B$ 有代价 $b_i$，对于某些物品对 $(i, j)$，若 $i$ 和 $j$ 不在同一集合，有额外代价 $c_{ij}$，求总代价最小的划分方案。

思路 ​

涉及到集合划分的，常见做法是最小割，因为最小割容易刻画“选择”。

套路的考虑让割边表示选择，构建源点 $s$ 和汇点 $t$。对于每个物品 $i$，从 $s$ 向 $i$ 连容量为 $a_i$ 的边，从 $i$ 向 $t$ 连容量为 $b_i$ 的边。对于存在代价 $c_{ij}$ 的物品对 $(i, j)$，在 $i$ 和 $j$ 之间连双向边，容量为 $c_{ij}$。通过求 $s$ 到 $t$ 的最小割，可得到最小总代价。

二分图最小点覆盖 ​

内容 ​

对于二分图 $G=(V = L\cup R, E)$，选出一个大小最小的点集 $S \subseteq V$，使得 $\forall (u, v) \in E$，都有 $u \in S$ 或 $v \in S$。

思路 ​

刻画选择，所以考虑最小割。

考虑什么时候不合法，就是一条边两个端点都不选。

构建源点 $s$ 和汇点 $t$，从 $s$ 向 $L$ 中每个点连容量为 $1$ 的边，从 $R$ 中每个点向 $t$ 连容量为 $1$ 的边。对于原图中的每条边 $(u, v)$，其中 $u \in L$，$v \in R$，从 $u$ 向 $v$ 连容量为 $+\infty$ 的边。通过求 $s$ 到 $t$ 的最小割，割边所关联的点集即为最小点覆盖集。

二分图最大独立集 ​

和最小点覆盖是补问题。即对于二分图 $G=(V, E)$，设最小点覆盖集为 $S$，则最大独立集为 $V - S$。

最大权闭合子图 ​

内容 ​

给定有向图 $G=(V, E)$，每个点 $v$ 有一个权值 $w(v)$，求一个子图 $G'=(V', E')$，其中 $V' \subseteq V$，$E' \subseteq E$，且对于任意 $(u, v) \in E$，若 $u \in V'$，则 $v \in V'$，使得 $\sum_{v \in V'} w(v)$ 最大。

思路 ​

刻画选择，考虑最小割。

先把最大转最小，设所有点权和为 $W = \sum_{v \in V} w(v)$，我们要最大化的是 $\sum_{v \in V'} w(v)$，那么等价于最小化 $W - \sum_{v \in V'} w(v)$。

构建源点 $s$ 和汇点 $t$，对于权值为正的点 $v$，从 $s$ 向 $v$ 连容量为 $w(v)$ 的边；对于权值为负的点 $v$，从 $v$ 向 $t$ 连容量为 $-w(v)$ 的边。原图中的边容量设为 $+\infty$。通过求 $s$ 到 $t$ 的最小割，$W$ 减去最小割的值即为最大权闭合子图的权值。

最小DAG路径覆盖 ​

不相交 ​

每个点恰被一条路径覆盖，求所需的最小路径数量。

思路 ​

限制难处理，考虑重新刻画。

点没前途，考虑边，发现限制就是每个点的入边选择数量 $\leq 1$ 且出边选择数量 $\leq 1$，然后要让选的边最多。

具体做法是将每个点 $v$ 拆成 $v_{in}$ 和 $v_{out}$，从 $s$ 向每个 $v_{in}$ 连容量为 $1$ 的边，从每个 $v_{out}$ 向 $t$ 连容量为 $1$ 的边。对于原图中的边 $(u, v)$，从 $u_{out}$ 向 $v_{in}$ 连容量为 $1$ 的边。通过求 $s$ 到 $t$ 的最大流 $f$，最小路径覆盖数为 $|V| - f$。

当然，直接做也可以，用最小费用最大流可以实现相同复杂度。

可相交 ​

将“恰”改为“至少”。

思路 ​

考虑刻画之，但没什么想法，尝试直接做。

DP不行，看网络流，这其实是有下界的最小流。

直接用上下界最小费用可行流即可。

当然，也可以考虑重新刻画路径的本质。

将所有点划分成若干集合，限制是集合内部的点满足相邻可达。

那我们只关心可达性，对原图进行传递闭包，设得到的图为 $G'=(V, E')$，然后在 $G'$ 上用不相交路径覆盖的方法求解。

切糕问题 ​

内容 ​

来自HNOI2013。

思路 ​

考虑直接做，dp几乎不可能，考虑用割刻画选择。

设有一个 $n \times m$ 的网格，每个网格点 $(i, j)$ 有 $1$ 到 $p$ 种取值，每种取值有不同的代价，同时存在一些限制条件，要求在满足限制条件下，选择一种取值方案使得总代价最小。

将待选的值 $[1, p]$ 顺次连成一条链，即对于每个网格点 $(i, j)$，从取值为 $k$ 的节点向取值为 $k + 1$ 的节点连容量为对应代价的边（$1 \leq k < p$）。对于不合法限制，通过连边刻画，例如如果限制 $(i_1, j_1)$ 和 $(i_2, j_2)$ 取值差不能超过某个值，可在相应取值节点间连容量为 $+\infty$ 的边。通过求最小割，可得到最小总代价。