浅谈网络流的各种建模方法

strcmp

2022-05-18 12:24:52

Algo. & Theory

\Large{\text{Part-1 目录}}

\text{Part-1 目录}
\text{Part0 前言}
\text{Part1 符号约定}
\text{Part2 各种模型}

\quad \small{\text{Part2.1 多源多汇建模}}

\qquad \scriptsize{\text{Part2.1.1 一般图多源多汇建模}}

\qquad \scriptsize{\text{Part2.1.2 二分图最大匹配建模}}

\qquad \scriptsize{\text{Part2.1.3 二分图最小顶点集覆盖 König 定理}}

\qquad \scriptsize{\text{Part2.1.4 二分图最大独立集}}

\quad \small{\text{Part2.2 最大流最小割定理}}

\qquad \scriptsize{\text{Part2.2.1 最小割定义及其证明}}

\qquad \scriptsize{\text{Part2.2.2 拆点法}}

\qquad \scriptsize{\text{Part2.2.3 染色法}}

\qquad \scriptsize{\text{Part2.2.4 划分问题}}

\qquad \scriptsize{\text{Part2.2.5 互不攻击问题}}

\qquad \scriptsize{\text{Part2.2.6 对偶图最短路}}

\quad \small{\text{Part2.3 路径覆盖与链覆盖}}

\qquad \scriptsize{\text{Part2.3.1 DAG 最小路径覆盖}}

\qquad \scriptsize{\text{Part2.3.1 DAG 最小链覆盖}}

\qquad \scriptsize{\text{Part2.3.1 DAG 最长反链}}

\quad \small{\text{Part2.4 分层图}}

\quad \small{\text{Part2.5 费用流}}

\qquad \scriptsize{\text{Part2.5.1 有负环的费用流}}

\qquad \scriptsize{\text{Part2.5.2 方格取数问题}}

\qquad \scriptsize{\text{Part2.5.3 区间模型}}

\qquad \scriptsize{\text{Part2.5.4 后效性模型}}

\qquad \scriptsize{\text{Part2.5.5 求最短/长往返路}}

\quad \small{\text{Part2.6 最大权闭合子图}}

\quad \small{\text{Part2.7 最大密度子图}}

\quad \small{\text{Part2.8 上下界网络流}}

\qquad \scriptsize{\text{Part2.8.1 无源汇上下界可行流}}

\qquad \scriptsize{\text{Part2.8.2 有源汇上下界可行流}}

\qquad \scriptsize{\text{Part2.8.3 有源汇上下界最大流}}

\quad \small{\text{Part2.9 隐式图}}

\quad \small{\text{Part2.10 枚举与二分}}

\qquad \scriptsize{\text{Part2.10.1 枚举}}

\qquad \scriptsize{\text{Part2.10.2 二分}}

\quad \small{\texttt{Part2.11 建模方法总结}}

\text{Part3 经典难题}

\quad \scriptsize{\texttt{Part3.1 P2172 部落战争}}

\quad \scriptsize{\texttt{Part3.2 P4542 营救皮卡丘}}

\quad \scriptsize{\texttt{Part3.3 P4003 无限之环}}

\text{Part4 后记}
\text{Part5 参考文献}
\text{Part6 Updata}
\text{Part7 Target}

\Large{\text{Part0 前言}}

网络流是图论算法中建模最有技巧和思维难度的算法之一，在网络上很难找到一篇系统的简述网络流建模方法的资料，所以写了这篇文章作为对网络流的常用建模方法的总结。

限于篇幅，本文主要讲建模方法，对于算法以及证明等涉及较少，如果还不清楚网络流的算法流程，请自行搜索资料，网络上不乏对算法有很好介绍的文章，个人比较推荐 qyf 大佬的日报文章。

为了统一格式，本文中出现的最大流代码均使用 ISAP 算法，费用流代码均使用多路增广 SPFA。使用的图如果为原创均使用 CS Academy、krita 或者画图 3D 制作，在后两者无法使用的时候会使用在线速写板，转载题解的图会标明原图作者。

由于笔者只是一个初一的蒟蒻（~~好的现在是初二了~~），本文的可能会有一些不太严谨甚至是错误的地方，对此深感抱歉。如果发现错误，恳请指出，非常感谢！

友链：附属题单

\Large{\text{Part1 符号约定}}

$\mathrm{G= \langle V,\,E \rangle}$ 表示图。 $u \to v$，$u$ 通过一条边直接到达 $v$。 $u \leadsto v$，$u$ 通过某条路径到达 $v$。 $u \not \rightarrow v$，$u$ 不存在到 $v$ 的边。 $u \not \rightsquigarrow v$，$u$ 不存在到 $v$ 的路径。 $\operatorname{c}(u,\,v),\;(u,\,v)\in {\mathrm{E}},\;\operatorname{c}(u,\,v) \ge 0$ 表示容量。 $s,\,s \in {\mathrm{V}}$ 源点。 $t,\,t \in {\mathrm{V}}$ 汇点。方便起见，如果 $(u,\,v) \notin {\mathrm{E}}$ 则 $\operatorname{c}(u,\,v) = 0$。方便起见，规定对每个结点 $u \in {\mathrm{V}}$ 都有一条路径 $s \leadsto u \leadsto t$，这个条件可以通过增加容量为 $0$ 的边实现。定义**艾佛森括号**，其定义如下： $$ \text{[p]} = \begin{cases}1 & \text{If p is true.} &(1) \\ 0 & \text{If p is false.} & (2)\end{cases} $$ 其中 $\mathrm p$ 为一个命题。 **接下来是流的形式化定义：** 设 $\mathrm{G= \langle V,\,E \rangle}$ 为一个流网络，$\mathrm G$ 中的**流**是一个实值函数 $\operatorname{f}:\;{\mathrm{V \times V} \to \mathbb R}$，满足如下两条性质： - **容量限制：** 对于 $\forall u,\,v \in {\mathrm{V}}$，有 $0 \le \operatorname{f}(u,\,v) \le \operatorname{c}(u,\,v)$。 - **流量守恒：** 对于 $\forall u \in {\mathrm{V}}-\{s,\,t\}$，要求： $$ \begin{aligned} & \sum_{v \in {\mathrm{V}}}\operatorname{f}(u,\,v)=\sum_{v \in {\mathrm{V}}}\operatorname{f}(v,\,u)& (1) \end{aligned} $$ 我们称非负值 $\operatorname{f}(u,\,v)$ 为从 $u$ 到 $v$ 的流。一个流的流值 $|f|$ 定义如下： $$ \begin{aligned} & |f| = \sum_{v \in {\mathrm{V}}}\operatorname{f}(s,\,v)-\sum_{v \in {\mathrm{V}}}\operatorname{f}(v,\,s) &(2) \end{aligned} $$ **最大流问题：** 给定一个特殊点 $s$ 和一个特殊点 $t$，找出从 $s$ 到 $t$ 的一个流 $\operatorname{f}(s,\,t)$，使得 $|f|$ 的值最大。 $\operatorname{c}_f(u,\,v),\;(u,\,v) \in {\mathrm{E}},\;\operatorname{c}_f(u,\,v) \ge 0$ 为残存容量，定义如下： $$ \operatorname{c}_f(u,\,v)=\begin{cases}\operatorname{c}(u,\,v)-\operatorname{f}(u,\,v) & \text{($u,\,v) \in {\mathrm{E}}$} &(1) \\ \operatorname{f}(u,\,v) & \text{($u,\,v) \notin {\mathrm{E}}$} & (2)\\ 0 & \text{other} &(3)\end{cases} $$ **残存网络** ${\mathrm{G}}_f$ 是只保留残存容量不为 $0$ 的边的网络，其中每条边的权值即为所对应边的残存容量。 **反向弧：** $\forall (u,\,v) \in {\mathrm{E}}$，都有一条 $v \to u$ 与其对应，其容量为 $\operatorname{c}(u,\,v)$，流量为 $\operatorname{c}_f(u,\,v)$。 **增广路径：** 从 $s$ 到 $t$ 的一条简单路径，该路径上每一条边的残存容量都不为 $0$。 **增广路定理：** 当流网络无法找出从 $s$ 到 $t$ 的增广路时，此时的 $|f|$ 即为最大流。方便起见，使用 $\mathrm{maxflow}$ 表示最大流，$\mathrm{mincost}$ 表示最小费用。方便起见，二分图的两个部分分别用 $\mathrm X$ 和 $\mathrm Y$ 代替，最小割割断的两个部分分别用 $\mathrm S$ 和 $\mathrm T$ 代替，规定 $s \in {\mathrm{S}},\,t \in {\mathrm{T}}$。 $\Large{\text{Part2 各种模型}}

\scriptsize{\text{网络流最迷人的地方在于那让人拍案叫绝的建模思想和以不变应万变的扩展性。}}

\large\text{Part2.1 多源多汇建模}

\scriptsize\text{多源多汇建模是区别于普通网络流的最基础的建模方法。}

\small{\text{Part2.1.1 一般图多源多汇建模}}

P1402 酒店之王

题目大意：有 p 个房间和 q 个菜品，给定 n 个客人喜欢的房间和喜欢的菜品，要求最大化能被满足的客人数量，即住上喜欢的房间且吃上喜欢的菜，每个房间和每个菜品只能匹配给一位客人，一位客人只能匹配一个房间和一个菜品。

看到这道题，考虑对房间和客人之间连边，客人与菜品之间连边，就可以转换为二分图最大匹配问题，跑两遍匈牙利算法即可。

但是，上述算法只能适用于没有奇数长度的环上的图上使用，可扩展性不高，但我们可以使用网络流算法以更优秀的复杂度解决这道题。

但是网络流只能用在只有一个源点和汇点的图上，于是考虑特殊建图。

更形式化的定义多源多汇网络流：给定一张图 \mathrm{G= \langle V,E \rangle}，同时给定 k 个特殊点 s_i \in {\mathrm{V}},\,i=1,\,2,\,3\cdots k 作为点集 \mathrm S 和 p 个特殊点 t_j \in {\mathrm{V}},\,j=1,\,2,\,3\dots p 作为点集 \mathrm T。定义该流网络的流值 |f| 为：

\begin{aligned} & |f| = \sum^{k}_{i=1}\sum^{p}_{j=1} \operatorname{f}(s_i,\,t_j) -\sum^{k}_{i=1}\sum^{p}_{j=1} \operatorname{f}(t_j,\,s_i),\;s_i\in {\mathrm S},\;t_j \in {\mathrm T} &(1.1) \end{aligned}

要求在满足约束的前提下，最大化 |f| 的值。

增加超级汇 s' 和超级汇 t'，从 s' 向每个 s_i 连容量为 +\infty 的边，从每个 t_i 向 t' 连容量为 +\infty 的边。

说人话就是假设你手上突然多出了两个结点，一个是 s'，一个是 t'。你从 s' 到每个 s_i 都连上容量为无穷大的边，从每个 t_i 到 t' 连容量为无穷大的边，然后向 s' 灌水，流就从 s' 开始向 s_i 流，s_i 又向其他结点流......一直流到 t'。

上一张比较鬼畜的图。

正确性可以感性理解，因为 s' 向 s_i 的连边容量是 +\infty 的，所以不可能被跑满，汇点同理，总流量仍然被其他点限制，故总流量与原图是一样的。

但是如果这样连边，我们仍然只能获得 60 分。这是因为有可能一位客人匹配到了多个房间和多个菜品，因此只有限制每位客人的流量才能通过全部数据，具体如何建模，请看 \text{Part2.2.2} 拆点部分。

\small{\text{Part2.1.2 二分图最大匹配建模}}

P2756 飞行员配对方案问题

这道题很明显是一道很裸的二分图，那网络流用在二分图上又要如何建模呢？

很显然，对二分图的建模可以直接规约为多源多汇网络流的特殊情况，即不存在长度为奇数的环，所以我们可以建立超级源点 s 对其 \mathrm X 部分结点连容量为 1 的边，建立超级汇点 t 并遍历每个 \mathrm Y 部分结点向 t 其连容量为 1 的边，然后正常连接读入的边，容量为 1，可以保证每个结点只匹配到一个结点，此时的 \mathrm {maxflow} 即为答案。

输出方案就从 \mathrm X 部分的结点一个个遍历，找出残余容量为 0 的边，然后输出对应结点。

顺道说一句，虽然 Dinic/ISAP 在一般图上的最坏时间复杂度是 \mathcal O(n^2m) 的，但是在二分图上就会变成 \mathcal O(m\sqrt n)，而且还跑不满，大多数情况下会比匈牙利算法快很多，具体~~我也不会证~~，感兴趣的可以去看一看证明。

参考代码

\small{\text{Part2.1.3 二分图最小顶点集覆盖 König 定理}}

\scriptsize{\text{本证明主要是从本人之前写的题解搬过来的，但之后可能会继续维护，原题解将不会维护，想要看原题解的 OIer 可以去翻下题的第一个题解。}}

UVA11419 SAM I AM

题目大意：给定一张 \mathrm {R \times C} 的网格图，同时给定 \mathrm N 个特殊的点，要求覆盖掉一些行和列，使得所有的特殊点都被覆盖，求最优方案，即使得被覆盖的行和列尽量少。

考虑二分图，在二分图 \mathrm {G= \langle X,\,Y,\,E \rangle} 中，使行对应 \mathrm X 结点，列对应 \mathrm Y 结点。当输入一个特殊点 v=(x,\,y) 时，则从 x 向 y 连一条权值为 1 的边，其中 x \in \mathrm{X},\, y \in \mathrm{Y}。

考虑二分图 \mathrm G 的性质，可以看到，题目中要求用最小的行和列覆盖掉所有特殊点的条件，可以转化为求在二分图 \mathrm G 上选择最小的点集，使得二分图 \mathrm G 中的所有边 e \in \mathrm E 至少与该点集中的一个点相连。

即可将条件转化为求二分图 \mathrm{G= \langle X,Y,E \rangle} 的最小顶点集覆盖。

二分图最小顶点集覆盖：

定义：

在二分图 \mathrm{G= \langle X,\,Y,\,E \rangle} 中求出最小的顶点集 \mathrm{V \subseteq \{X \cup Y\}}，使得 \forall e \in \mathrm E 都至少与一个顶点 v \in \mathrm V 相关联。

\mathrm{König} 定理：二分图最小顶点集覆盖数 \text{=} 二分图最大匹配数。

\mathrm{König} 定理证明：

设 \mathcal M 为二分图最大匹配数，\mathcal C 为二分图最小顶点集覆盖数。

首先一个显然的结论：

引理 1：\mathrm{\forall G = \langle X,\,Y,\,E \rangle},\,\mathcal{C \ge M}

根据顶点集覆盖的定义，每个匹配边必须被覆盖，且每个匹配边不会相交，所以必有 \mathcal{C \ge M}。

更进一步，证明：

\begin{aligned} & \mathrm{\forall G = \langle X,\,Y,\,E \rangle},\,\mathcal{C = M} & (1.2) \end{aligned}

考虑对匈牙利算法求最大匹配的过程做如下改动：

顺着匈牙利算法的交错路上的点，将这些点集全部打上标记，直到无法找出增广路。
将 \mathrm X 点集中被打了标记的点与 \mathrm Y 点集中没被打上标记的点组成一个新的点集 \mathrm V。

点集 \mathrm V 就是一种可行的顶点集覆盖，其覆盖数为 \mathcal M，且是一个最小顶点集覆盖。

引理 2： 点集 \mathrm V 是一个顶点集覆盖。

证明：

考虑将边分为在交错路上的边和不在交错路上的边。

结论 1： 在交错路上的边，可以覆盖对 \mathrm X 部分打了标记的点来将其覆盖。
结论 2： 对于不在交错路上且没有被覆盖到的边，其 \mathrm Y 部分的点肯定是未被标记的。

考虑反证法，如果当前边 e = u \to v 在 \mathrm Y 部分的结点 v 是被标记的，则由于当前边不在交错路上，其在 \mathrm X 部分的结点 u 一定是没有被标记的。

假设 e 为匹配边，则 v 在交错路上，但 u 不在交错路上，因为当前边为匹配边，故两者应该都在交错路上，矛盾。

假设 e 为非匹配边，则 v 到 u 的交错路可以继续走，e 也应该在交错路上，矛盾。

故结论 2 成立。

因为结论 1,\,2 都成立，故覆盖了点集 \mathrm{V} 则所有边都被覆盖，即点集 \mathrm{V} 是一个顶点集覆盖。

故引理 2 得证。

引理 3： 点集 \mathrm V 的大小 \mathcal{C = M}。

证明：

因为每条匹配边从 \mathrm X 点集中被标记的结点出发，且不可能存在被标记的点不在匹配边上的情况，故 \mathrm X 部分中被标记的结点的个数与匹配边数量相等。

又因为交错路的标号方式，交错路上的边的两端的结点必定都被标记过，故非交错路上的未被覆盖的边的 \mathrm Y 点集部分的端点一定是未被标记的，因为前面的结论，每个未被标记的 \mathrm Y 部分的点必定会连且只会连出一条匹配边，与 \mathrm X 部分的被标记的点一一对应。

故点集 \mathrm V 的大小 \mathcal{C = M}。

由引理 1,\,2,\,3 立得 \mathrm{König} 定理。

\text{Q.E.D.}

接下来就是输出方案的问题了，我们从每个结点开始 \text{dfs}，只走残余容量不为 0 的边，然后沿途标记并输出当前结点即可，

参考代码

\small{\text{Part2.1.3 二分图最大独立集}}

\scriptsize{\text{二分图最大独立集没有什么很合适的板子，主要作为二分图最小顶点集覆盖的补充。}}

二分图最大独立集：

定义：

在二分图 \mathrm G = \langle \mathrm{X,\,Y,\,Z} \rangle 中，选取一个点集 \mathrm V \subseteq \mathrm G，使得 \forall u,\,v \in \mathrm V，有 u \not \to v，则称 \mathrm V 为原图的一个独立集，在满足上述条件的基础下，最大化 \mathrm V 的大小，此时则称 \mathrm V 是二分图 \mathrm G = \langle \mathrm{X,\,Y,\,Z} \rangle 的一个最大权独立集。

一般的，我们有最大权独立集点数等于总点数减去最小顶点集覆盖。

证明：

引理 1： 对于一个二分图 \mathrm G = \langle \mathrm{X,\,Y,\,Z} \rangle，若已求出该二分图的一个顶点集覆盖 \mathrm V，则 \complement_{\mathrm {X \cup Y}}\mathrm V 形成一个独立集。

观察求解顶点集覆盖后的情况，对于顶点集的补集 \complement_{\mathrm {X \cup Y}}\mathrm V，我们从中任取两点 u,\,v，则原图必然不存在 u \to v 或 v \to u，因为若存在该连边，则 u \to v 或 v \to u 没有被覆盖，该顶点集覆盖必定不合法。故 \complement_{\mathrm {X \cup Y}}\mathrm V 中任意两点之间不存在连边，满足独立集的定义，故该点集是一个独立集。

引理 2： 任意独立集有且仅有一个顶点集覆盖与其对应，且是其补集。（引理 1 的逆定理，留给读者自证）

引理 3： 对于二分图 \mathrm G = \langle \mathrm{X,\,Y,\,Z} \rangle，若已求出该二分图的一个最小顶点集覆盖 \mathrm V，则 \complement_{\mathrm {X \cup Y}}\mathrm V 形成一个最大权独立集。

根据引理 1，得到 \complement_{\mathrm {X \cup Y}}\mathrm V 是一个独立集；又根据引理 2，每一个独立集都对应于一个顶点集覆盖，且其点数为总点数减去顶点集覆盖数。因为总点数为常数，如要最大化点集 \mathrm V 的大小，则需要使得对应顶点集覆盖最小，又因为最小顶点集覆盖的最优性，选取最小顶点集覆盖的补集为最大权独立集，显然，这是最优的。

根据引理 2,\,3，易证得最大权独立集点数等于总点数减去最小顶点集覆盖。

\text{Q.E.D.}

\large\text{Part2.2 最大流最小割定理}

\scriptsize\text{最大流 = 最小割是网络流算法中的重要结论，通过运用该定理，我们可以解决一些复杂的划分问题。}

\text{Part2.2.1 最小割定义及其证明}

定义图 \mathrm{G= \langle V,\,E \rangle} 的割函数 \operatorname{cut}(s,\,\mathrm{G},\,t): \mathrm G\to \mathrm{C} 为原图上的一个边集 \mathrm{C \subseteq E}，满足在原图中删去该边集后，有 s \not \leadsto t，此时称边集 \mathrm{C} 为图 \mathrm{G= \langle V,\,E \rangle} 的一个割，说人话就是将整张图切成两半，一半是 \mathrm S 部分，一半是 \mathrm T 部分。显然相同的 s 和 t 之间可能有多个不同的割。

最小割问题就是在所有 \operatorname{cut}(s,\,\mathrm{G},\,t) 中找到一个割，使得该割所包含的边的权值之和 |\mathrm{C}| 最小，则称该割为图 \mathrm{G= \langle V,\,E \rangle} 的一个最小割，说的清楚点就是假设切断每条边有一个代价。你要做的就是想办法将图切开的同时，还要保证所花费的代价最小。方便起见，将其权值用 \mathrm{mincut} 表示。

最大流最小割定理： 对于 \forall \mathrm{G= \langle V,\,E \rangle}，必有 \mathrm{maxflow=mincut}。

证明~~没有人话~~，可选择性观看。

最大流最小割定理证明：

引理 1： 对于 \forall \mathrm{G= \langle V,\,E \rangle},\; \forall \mathrm{C} \in \operatorname{cut}(s,\,\mathrm{G},\,t)，必有 \mathrm{maxflow \le |C|}。

证明：设割 \operatorname{cut}(s,\,\mathrm{G},\,t) 根据截断的边将图分为 \mathrm S 部分和 \mathrm T 部分，其中 s \in \mathrm S,\, t \in \mathrm T。

\begin{aligned} &\mathrm{maxflow} = \sum_{u \in {\mathrm{V}}}\operatorname{f}(s,\,u)-\sum_{u \in {\mathrm{V}}}\operatorname{f}(u,\,s) &(1.3.1)\\ & = \sum_{u \in {\mathrm{V}}}\operatorname{f}(s,\,u)-\operatorname{f}(u,\,s) &(1.3.2)\\ & = \sum_{u \in \mathrm S}\left(\sum_{v \in \mathrm S}\operatorname{f}(u,\,v)+\sum_{v \in \mathrm T}\operatorname{f}(u,\,v)-\sum_{v \in \mathrm S}\operatorname{f}(v,\,u)-\sum_{v \in \mathrm T}\operatorname{f}(v,\,u)\right) &(1.3.3)\\ & = \sum_{u \in \mathrm S}\sum_{v \in \mathrm S}\left(\operatorname{f}(u,\,v)-\operatorname{f}(v,\,u)\right)+\sum_{u \in \mathrm S}\sum_{v \in \mathrm T}(\operatorname{f}(u,\,v)-\operatorname{f}(v,\,u)) &(1.3.4)\\ & \because \sum_{u \in \mathrm S}\sum_{v \in \mathrm S}\operatorname{f}(u,\,v)=\sum_{u \in \mathrm S}\sum_{v \in \mathrm S}\operatorname{f}(v,\,u) &(1.3.5)\\ & \therefore \sum_{u \in \mathrm S}\sum_{v \in \mathrm S}(\operatorname{f}(u,\,v)-\operatorname{f}(v,\,u))=0 &(1.3.6)\\ & \therefore \sum_{u \in \mathrm S}\sum_{v \in \mathrm S}(\operatorname{f}(u,\,v)-\operatorname{f}(v,\,u))+\sum_{u \in \mathrm S}\sum_{v \in \mathrm T}(\operatorname{f}(u,\,v)-\operatorname{f}(v,\,u)) = \sum_{u \in \mathrm S}\sum_{v \in \mathrm T}(\operatorname{f}(u,\,v)-\operatorname{f}(v,\,u)) &(1.3.7)\\ & \because \sum_{u \in \mathrm S}\sum_{v \in \mathrm T}(\operatorname{f}(u,\,v)-\operatorname{f}(v,\,u)) \le \sum_{u \in \mathrm S}\sum_{v \in \mathrm T}\operatorname{f}(u,\,v) \le \sum_{u \in \mathrm S}\sum_{v \in \mathrm T}\operatorname{c}(u,\,v) &(1.3.8)\\ & \therefore \mathrm{maxflow} \le |\mathrm C| &(1.3.9) \end{aligned}

故图中 s 到 t 的最大流严格不大于割的容量，证毕。

引理 2： 对 \mathrm{G= \langle V,\,E \rangle} 求解最大流后，设边集 \mathrm{F}=\{\operatorname{c}_f(u,\,v)=0 \mid \forall u \to v \in \mathrm{E}\}，则 \mathrm{F} 是原图的一个割。

证明：

考虑反证法。

经过最大流的求解后，原图中已经不存在增广路，显然任意一条 s \leadsto t 路径上都必然有一条残余容量为 0 的边，将这些边删去后如果存在 s \leadsto t 路径，则还有增广路，与原图不存在增广路矛盾，故必然不存在 s \leadsto t 路径，满足割的定义，因此点集 \mathrm{F} 是原图的一个割，引理得证。

由引理 2 得到 \mathrm{F} 是一个割，引理 1 得到该点集权值大小不大于任意一个割，因此点集 \mathrm{F} 是原图的一个最小割。

总证明：

因为点集 \mathrm{F} 是原图的一个最小割，设原图有一个流使得 |\operatorname{f}(s,\,t)| = |\mathrm{F}|，由引理 1 得到 \operatorname{f}(s,\,t) 是原图的一个最大流，又因为最大流值不大于任意割的权值，如果上述流不存在，则最大流值比最小割值更小，其所形成的割权值小于最小割，与 \mathrm{F} 是原图的一个最小割矛盾，因此上述流必然存在，因此对于 \forall \mathrm{G= \langle V,\,E \rangle}，必有 \mathrm{maxflow=mincut}。

\text{Q.E.D.}

\text{Part2.2.2 拆点法}

\scriptsize \text{拆点法本质上是一种将点的限制转化为边的限制的一种方法。}

在 \text{Part2.1.2} 中，我们讨论了 P1402 的建模方法，并且发现会存在有游客占用多个房间和菜品的情况，这种情况下我们只能通过限制通过游客的流才能避免这种情况。

显然可以分类讨论，但如果这样扩展性仍然不高。

形式化的解释，对结点 u 的容量进行一个大小为 k 的限制，使得 0 \le f(s,\,u) \le k。

如果将一个点拆分成两个点就好办了。

形式化的讲，将一个结点 u \in {\mathrm V} 拆分为 u' 和 u''，所有到达 u 的边 v \to u,\;v \in {\mathrm V} 都转化为连向 u' 的边，所有从 u 出去的边 u \to v,\;v \in {\mathrm V} 都转化为从 u'' 出去的边，最后从 u' 向 u'' 连一条容量为 k 的边即可。

容易证明，通过结点 u 的流 |f| 不可能超过 k。

这种方法就叫做网络流的拆点法。

形象化的理解，放图。

经过拆点后，就变成了这个样子。

拆点法最常用于限制点权（相当于割点），通过建立虚点，成功的将点上的限制转化为边上的限制，我们可以对这个边乱搞，比如加上费用就可以模拟加上点权，在此基础上加上容量为 +\infty 的边跑费用流可以模拟每个点允许通过多次等等。

对于这道题，我们将客人拆分为两个点，之间连容量为 1 的边，然后入边连入点，出点连出边，容量都为 1，能通过全部数据。

参考代码

不过考虑到一些情况，先把拆点的板题放上：

P1345 奶牛的电信

题目大意：给定一张 n 个结点的图，可以花费 1 的代价将一个结点从图中删去，求出一个最优方案，使得被删去的结点数目尽量小，且使得给定的两点 c_1 和 c_2 之间不存在任何路径，即使得 c1 \not \leadsto c_2。

根据上述内容，我们将点 u 拆分为点 u' 和点 u''，u' 肯定向 u'' 连容量为 1 的边（每个结点只会被删一次）。这样，被割的时候，入边的流肯定是没办法从出边流出了。将给定的两个特殊点作为 s 和 t，即将 c_1' 作为 s，将 c_2'' 作为 t，最后直接跑网络流即可。

其实还有一个小细节，那就是特殊点的入点和出点之间的容量应该设为 +\infty，而各个结点之间出点连向入点的边的容量不限（只要不小于 1 即可）。

第一点较为显然，但第二点的思考相对更有难度一点，读者可自行证明。

参考代码

接下来是一种更新奇的拆点问题：按时间拆点。

上一道例题，我们只是讲了最基础的拆点方法，即入点与出点的拆点法。但实践中往往会遇到一些更毒瘤的题，使得我们不得不拆更多的点，而按时间拆点就是其中的一种。

先看一道例题：P2053 [SCOI2007] 修车

题目大意：有 \mathrm N 辆车和 \mathrm M 位技术人员，每位技术人员对不同的车所需的维修时间是不同的，要求安排一个合适的修车方案，使得顾客等待的平均时间最短。

显然，使得平均时间最短也就是使得总时间最短，然后用总时间除以 \mathrm N 就是平均时间。

考虑一位技术人员的修车顺序为 \{1,\,2,\,3,\,\dots,\,k\}，其修每个车所花费的时间为 \{w_1,\,w_2,\,w_3,\,\dots,\,w_k\}，则其对等待总时间的贡献为 k \times w_1 + (k - 1) \times w_2 + (k - 2) \times w_3 + \dots + w_k，即 \sum^{k}_{i=1}{(k - i + 1) \times w_i}。

接下来，我们将每个技术人员拆成 \mathrm M 个结点 u_{ij}，代表第 i 位技术人员修第 j 辆车时的状态，因为只有这样，我们才能将上述贡献表示出来。建立超级源汇 s 和 t，显然 s 向每个客户代表的结点连容量为 1 的边，每个结点 u_{ij} 向 t 连容量为 1 的边。

现在仅仅用流难以表示贡献，于是加上费用表示贡献。

然后就是一个三重循环，每个客户结点向每个 u_{ij} 连容量为 1，费用为 j \times w_i 的边，接着跑最小费用最大流，费用除以 \mathrm N 即为答案。

参考代码

\text{Part2.2.3 染色法}

P2774 方格取数问题

题目大意：给定一张带点权的 n \times m 的网络图，要求取出一些结点，使得贡献最大，要求被取的结点不能相邻。

不能取相邻结点这个条件很难直接模拟，所以我们转化一下题目，先求出不取的方格的贡献，然后用总贡献减去该贡献，剩下的就是取出的方格的贡献。

如何模拟题意呢？可以看到，相邻的方格一定是不能取的，所以我们必须要把相邻方格分到不同的点集里。

手推一下，可以发现，如果像国际象棋那样把整个网络图染成黑白相间的，则相邻结点必然颜色不同，对应到代码上就是当 x + y \equiv 1\pmod{2} 时将结点 (x,\,y) 染成黑色，否则染成白色。

用最小割表示取与不取，从超级源点 s 向所有黑点连容量为该点贡献的边，所以黑结点向相邻白结点连容量为 +\infty 的边，最后所有白点向超级汇点 t 连容量为该点贡献的边，此时要么是源点出去的边被割，要么是到汇点的边没割，此时的最小割就是所有不被取出的方格的总贡献。

为什么？我们这里其实用了一个技巧，将被割掉的边表示为不选这个点，什么意思呢？假设一个黑点 u，s \to u 的这条边因为走了其他白点而满流了，那么我们就不会选择这个点 u；如果 u 是白点，u \to t 的这条边满流了，我们也不会选择这个点。而黑点到白点的边是不可能被割掉的。（因为容量为 +\infty）

首先，我们证明这个方案的合法性，考虑反证法，如果跑完最小割之后存在两个互斥的结点 u 和 v，显然 u,\,v 颜色互异。假设 u 为黑点，v 为白点，则 s \to u 这条边与 v \to t 这条边都存在且容量不为 0。此时则存在一个权值大于 0 的增广路 s \to u \to v \to t，与最大流后不存在增广路矛盾，因此 s \to u 和 v \to t 中必然有一条边被割掉（不可能割掉 u \to v 这条边，还是因为容量为 +\infty）。因此该方案是严格满足合法性的。

再来证明这个方案的最优性：

引理 1： 任意割按照上述方法选取之后，必然满足合法性。

证明显然，与上例类似，只需将最小割替换为任意割即可。

引理 2： 引理 1 的逆命题，任意合法方案必定对应于一个割。

反证法，假设当前方案不与任意一个割相对应，则选取之后必然有相邻结点被选择，才能保证当前方案不是一个割，而由于相邻结点不能被选取，因此该方案不满足合法性，因此任意合法方案必定对应于一个割。

引理 3： 任意合法方案的权值（即不选取该方案的结点后，其余结点的权值和）等于总权值减去与之对应的割的权值。

显然，该引理等价于任意合法方案所包含的点权值等于与之对应的割的权值。

假设当前结点 u 包含于该方案中，分两种情况讨论：

因为对答案的贡献与结点 u 权值相等，因此任意合法方案所包含的点权值等于与之对应的割的权值。

引理 3 得证。

总证明：

根据引理 2，任意合法方案对应于一个割，又根据引理 3，该合法方案的权值与总权值减去与之对应的割的权值相等，显然结点的总权值 w 为一常数。则要使得方案最优，即使得该方案对应的割权值最小，也就是使得 w - |\mathrm C| 显然最小割满足该条件，又因为引理 1，最小割必定对应了一个合法方案，因此该方案同时具有合法性和最优性，该方案为一个最优方案。

\text{Q.E.D.}

参考代码

黑白相间的染色法是最常用的染色法，但是实践中往往有很多中染色方法，只有留心观察题目性质，才能确认题目要用到的染色方法。

\text{Part2.2.4 划分问题}

P4313 文理分科

题目大意：全班分科，每位同学分到文科能获得一定满意值，分到理科能获得一定满意值，如果上下左右的同学都被分到同一科也能增加一定的满意值，要求找到最优划分，使得满意值最大。

最经典的划分问题就是非黑即白，被割到 \mathrm X 集的就是选择 \mathrm X 集，被割到 \mathrm Y 集的就是选择 \mathrm Y 集。

继续运用正难则反的思想，我们先将源点连向当前结点，容量为选文科的贡献，当前结点连向汇点，容量为选理科得到的贡献，如果其中有一条边被割了，就说明不选该科。

对于文科的同时选择，我们考虑对每个点建立虚点，从当前结点向虚点连容量为 +\infty 的边，从 s 向虚点连容量为同时选的贡献的边，然后从虚点向周围点连容量为 +\infty 的边。

理科相反处理，从虚点向当前结点连容量为 +\infty 的边，从虚点向 t 连容量为同时选的贡献的边，然后周围点向虚点连容量为 +\infty 的边，这样可以保证同时选文科和同时选理科中必然有一边被割掉，也就不选该边。

最后用总贡献减去最小割，即为答案。

为什么这样是正确的呢？

我们还是依照了上一节的思路，用割表示不选当前结点，先假设不存在相邻同学选择同一科的时候的额外满意度，则该方法的正确性是显然的。（仿照上一节）

如果加上了这个额外的贡献呢？形式化一下，如果当前结点的周围结点只要有一个点被割，则该贡献代表的虚点也要被割，如何模拟这种情况，是本题的关键。

我们考虑上述建边方法的正确性，考虑文科集合的结点 u，假设结点 u 被割，同时 s 连向新建立的虚点 u' 的边的容量为 w。结点 u 有连向 u' 的边，容量为 +\infty，并且结点 u 与一个理科集合的结点 v 有一条容量为 +\infty 的边，v 与 t 的连边的残余容量为 d。

分两种情况：

第一种情况很好解释，就是该贡献作废；但第二种情况又是什么回事呢？

那就是我们发现选择文科比选择理科更加划算，因为此时额外贡献加上文科贡献大于理科贡献，所以暂时选择了文科。

接下来理科的连边分类讨论即可。

容易发现，划分问题的一般套路就是运用正难则反的思想，用 s 到 t 之间的最小割代表划分，同时建立虚点以满足题目所给的特殊条件，再用总贡献减去最小割，即为最优划分。

参考代码

\text{Part2.2.5 互不攻击问题}

P3355 骑士共存问题

题目大意：在一张 n \times n 的棋盘上放尽可能多的骑士，其中有些格子不能放，求最大方案。

我们发现仍然可以使用划分问题的思想来建图，还是正难则反的思想，考虑每个骑士能攻击到的格子，发现如果对其黑白染色还是能够符合要求，比如将上图的黄色视为黑色，红色视为白色，我们发现一个骑士的攻击范围恰好都是与其颜色不同的格子。

老套路，从 s 向所有黑点连容量为 1 的边，所有白点向 t 连容量为 1 的边，然后每个黑点向能攻击到的点连容量为 +\infty 的边，最后用总格数减去删除的格子再减去最小割就是答案。

证明与 \text{Part2.2.3} 类似，留给读者自行证明。

其实互不侵犯问题建立成二分图就可以规约为二分图最大独立集问题，使用匈牙利算法解决，有兴趣可以看看。

参考代码

上面的例题太入门了，来看一道稍微难一点的题。

P5030 长脖子鹿放置

几乎与上题一模一样，但唯一的不同就是长脖子鹿是“目”字的走法，如果强行黑白染色，我们会发现长脖子鹿刚好只能攻击到相同颜色的格子。

这下“黑白相间”染色行不通了，注意我这次把“黑白相间”故意提出来，是因为其他的黑白染色还是可以做到使得长脖子鹿只能攻击到不同颜色的格子的。

黑白相间染色虽然是最常见的染色法，在这种场景下却失效了，所以我们观察长脖子鹿能攻击到的结点的行数规律，显然长脖子鹿只能攻击到往外数第一行和第三行的格子，我们发现这些数字都是奇数。

如果我们按照行奇偶性染色，如果当前行是黑色，往外数第一行和第三行都是白色。

于是我们可以通过行奇偶性染色，将奇数行的结点归入 \mathrm X 集，偶数行的结点归入 \mathrm Y 集，然后跑最小割，答案仍然是总点数减去删除点数再减去最小割。

参考代码

\text{Part2.2.6 对偶图最短路}

概念引入：

平面图： 对于一个图 \mathrm{G= \langle V,\,E \rangle}，如果其同构图或其本身没有任何一边与其余边相交，则称图 \mathrm G 为一个平面图。
对偶图： 对于一个平面图 \mathrm{G= \langle V,\,E \rangle}，存在一个图 \mathrm{G'= \langle V',\,E' \rangle} 与 \mathrm G 形成映射关系，并满足如下性质：

由上述性质可知，对于 \forall \mathrm{G= \langle V,\,E \rangle}，\mathrm{G} 是一个平面图，则有且仅有一个 \mathrm {G'=\langle V',\,E' \rangle}，使得 \mathrm G' 是 \mathrm G 的对偶图。

对偶图的性质非常好，一般的，对偶图最短路与平面图最小割相等。

P2046 海拔

题目大意：在带边权的一个平面图上，图中结点有任意高度，起点高度为 0，终点高度为 1，爬坡要花费体力，下坡和平地不需要花费体力，要求在最理想的情况下（可以假设任意结点高度），到达终点的最小花费。

先推一个贪心的结论：每个结点的高度都只可能为 1 或者是 0，不可能出现其他值。

感性理解，每次下坡都只是不用花费，每次上坡都要花费，如果高度高完全没有益处，不满足最优性。

可以将问题转化为用最小的代价，将图分为两个点集。

这就是很裸的最小割，但是这道题数据范围很大，几乎可以到达百万级别。使用 Dinic/ISAP 跑最小割的最坏时间复杂度是 \mathcal O(n^2m) 的，虽然实践中几乎不可能跑满，但仍旧很可能被卡，有些时候我们需要在数据规模极大的平面图中跑最小割，这个时候暴力网络流显然时间复杂度难以承受，但是平面图是一种很特殊的图，我们可以使用间接的方式取得最小割。

显然，我们可以使用对偶图解决这道模板题。

但问题来了，我们要以哪个点开始跑最短路呢？显然先拆点，从 s 开始跑最短路，求 s \leadsto t 的最短路径长度。但初始两个点都没有连任何一条边，要怎么办呢？

因为我们要求从左上角到右下角的最小割，我们要么从右上角走到左下角，要么从左下角走到右下角，才能将原图“拦腰截断”，因此我们可以这样考虑：

位于原图最上方的边，显然有且仅有一个面与其相邻，因此该面对应的结点必然有一条自环，位于最右方的边同理，我们将原本的从 u 到 u 的自环边删去，然后改为从 s 到 u 的边，权值不变；位于最左方或者最下方的结点则与 t 相连，权值也不变。其余边则按照对偶图的规则建立，跑从 s 到 t 的最短路即可。

方便起见，这里假设一对结点之间的边的权值是一样的。

黑色的是原图，绿色的是对偶图。

对于这道题，我们类似将边旋转 90 度，然后到边界了就连超级源点 s 或超级汇点 t，最后跑 Dijkstra，到 t 的最短路径长度即为答案。

最后，由衷建议各位将要进队的选手们，如果遇到了平面图最小割，一定要打对偶图最短路，有可能这几十分就是进队与不进队的差别。

参考代码

\large\text{Part2.3 路径覆盖与链覆盖}

\text{Part2.3.1 DAG 最小路径覆盖}

\scriptsize{\text{用尽可能少的路径覆盖掉整张 DAG。}}

P2764 最小路径覆盖问题

DAG 的最小路径覆盖的定义就是每次可以从任意点出发，用尽可能少的不相交的路径覆盖掉整张 DAG。

我们可以考虑将每个结点看做一个路径，每个相邻结点可以合并，此时路径长度就会减少，因此我们应该最大化可合并的相邻结点的个数。

最大化可以合并的点数，有二分图最大匹配的味道了。

将每个点 u \in {\mathrm V} 拆成 u' 和 u''，分别为 \mathrm X 点集和 \mathrm Y 点集。每次处理形如 u \to v 的连边就将 u' 连向 v''，这时候跑二分图最大匹配，就是最大的可合并的点数，用总点数减去最大匹配数，就是最小路径覆盖总数。

输出方案就是从每个 \mathrm X 点集的点出发，输出当前结点，并递归遍历出边对应结点的 \mathrm X 部分的结点，注意不要访问已经访问过的结点。

下面是对该结论的严格证明，

正确性证明：

以下的图指上述算法建成的二分图，并且去掉超级源汇。

引理 1： 对于任意路径上的结点 u，u 的入度不大于 1，出度也不大于 1。

考虑反证法，显然路径与路径之间不会相交，假设当前结点 u 的入度大于 1，即有大于 1 个路径需要进入点 u，显然这些路径相交于点 u，与上述条件矛盾，于是结点 u 的入度不大于 1。结点 u 的出度的证法与之类似。

引理 2： 对于任意路径的起点 s_i 与终点 t_i，s_i 的入度必然为 0，t_i 的出度必然为 0。

证明较为简单，这里留给读者证明，读者可结合引理 1 进行证明。

接下来我们可以着手开始进行证明。

总证明：

在由上述算法构造出的二分图 \mathrm {G = (X,\,Y,\,Z)} 中，对于任意一个结点 u' \in \mathrm X，如果 u' 的出度为 0，则 u' 必定不与任何一个结点 v'' \in \mathrm Y 匹配，故 u' 是一个未匹配结点。

对该图进行二分图最大匹配，最大化匹配结点即最小化出度为 0 的结点，最小化出度为 0 的结点即最小化路径条数。

因此，该 DAG 上的最小路径覆盖等于该二分图上的最小未匹配数，即总点数减去最大匹配数。

\text{Q.E.D.}

参考代码

$\text{Part2.3.2 DAG 最小链覆盖}

模板题：POJ2594

在一个 DAG 中找出最少的路径，使得这些路径覆盖了所有的结点，路径之间可以相交。

可以看到，最小链覆盖与最小路径覆盖非常相近，考虑将最小链覆盖转化为最小路径覆盖。

先介绍算法：使用 Floyd-Warshall 算法对原图求出传递闭包，求出原图的传递闭包后，直接在传递闭包上跑最小路径覆盖即可。

感性证明：

每一个路径覆盖对应着一条链，链上相邻的结点所经过的路径没有对相交的限制，故这种方法避开了最小路径覆盖的限制。

\text{Part2.3.3 DAG 最长反链}

P1020 [NOIP1999 普及组] 导弹拦截

题目大意：给定一个正整数序列 a，求其 最长不上升子序列（LNIS）的长度 以及 将整个序列由最长不上升子序列覆盖的最小个数。

显然，考虑 dp 求解第一问，经过思考后可推导出状态转移方程：

\operatorname f(i) = \max\limits_{j < i \wedge a_j \ge a_i} \operatorname f(j) + 1

其中 \operatorname f(i) 的初始状态为 1，表示考虑从 i 开始新起一段不上升子序列。

考虑第二问的求解，观察第二问的本质，如果将满足 i < j \wedge a_j \ge a_i 的结点 i 和 j 之间连一条有向边 i \to j，形成一个图（显然，由不下降子序列的单调性，该图为一个有向无环图），则第二问的本质含义就是求解该图上的最小链覆盖。

显然的一点，我们可以直接建图，跑网络流求解即可。但是，由于该图点数是 \mathcal O(n) 的，即使就算传递闭包的 \mathcal O(n^3) 也难以承受。

也许可以使用 \mathrm {bitset} 优化传递闭包，并使用网络流求解最小链覆盖，时间复杂度是 \Theta(\dfrac{n^3}{w} + m\sqrt n) 的，其中 m 是满足 i < j \wedge a_j \ge a_i 的 (i,\,j) 对数，可近似看做 n^2。

经过计算之后，我们发现上述算法最坏情况下的运算量是 3 \times 10^8 级别的，时间很危险，也并不优美。

其实可以发现，如果两个链相交，第二问的答案并没有更优，所以可以删去传递闭包，直接跑最小路径覆盖。

然而因为空间和常数的问题，网络流算法最多只能获得这道题的 70 分。虽然将网络流改为二分图最大匹配的匈牙利算法可以通过本题，但代码复杂度过高，也不够简洁。

考虑优化，经过打表试验后，我们发现 第二问的答案即为原序列上的最长上升子序列（LIS）的长度。 我们可以考虑扩展这个结论。

接下来引入几个概念：

偏序集： 给定全集 \mathrm S，若该集合上存在二元关系 \le，满足：

自反性：\forall u \in \mathrm S \wedge u \le u。
传递性：\forall u,\,v,\,z \in \mathrm S,\; u \le v \wedge v \le z \iff u \le v \le z。
反对称性：\forall u,\,v \in \mathrm S,\; u \le v \wedge v \le u \iff u = v。

此时称二元组 (\mathrm S,\,\le) 为一个偏序集，注意 \le 仅仅是一个二元关系，并非所谓的小于或等于符号。

方便起见，设偏序集 \mathrm F = (\mathrm S,\,\le)。

全序集： 若偏序集 \mathrm F，对于 \forall u,\, v \in \mathrm F，有 u \le v \vee v \le u，则称偏序集 \mathrm F 为一个全序集。

链：偏序集 \mathrm F 的一个子集，满足该集合为一个全序集。

反链： 偏序集 \mathrm F 的一个子集，满足其任意非空子集都不为全序集。

链覆盖： 偏序集 \mathrm F 的若干条链，满足这些链的并集为 \mathrm F，且两两之间的交集为 \emptyset。（注意这与之前链覆盖的定义不同）

最长反链： 偏序集 \mathrm F 中长度最长的反链，可能有多个。

\mathrm{Dilworth} 定理：最小链覆盖大小等于最长反链长度。

观察这道题，可以看到最长反链即是原序列的最长上升子序列，所以原序列最长上升子序列的长度即为第二问的答案。

参考代码

对 \mathrm{Dilworth} 定理在网络流的运用：

P4298 [CTSC2008]祭祀

\large{\text{Part2.4 分层图}}

\scriptsize{\text{将状态建成不同的图层，即为分层图，网络流建模中下我们多以时间分层。}}

分层图更多的时候是用在最短路上，对于网络流的应用并不多，所以只讲一道例题。

P2754 家园/星际转移问题

对于这道题，我们发现太空船的连边非常特殊，甚至会因为时间而改变，很难处理。

但是我们观察到数据范围出奇的小，也许我们可以枚举时间，将图分层，然后动态加边跑网络流，当能够到达月球的人数大于或等于 k 的时候退出，输出答案。

话虽如此，但实际操作起来细节很多，因为我们并不知道具体时间，所以不能一次性将图建立出来，而是动态开点，动态加边。

首先将 s 连向当前时刻的地球，当前时刻的月球连向 t，通过太空船从上一时刻的太空站转移到当前时刻的太空船，然后继续跑最大流，一直到结束条件被满足就直接退出。

样例对应的图大概是这样的：

对于无解的判定，参考代码是当总迭代次数大于某个数的时候判定无解，但这种方法效率不高，还容易错判，因此更好的方法是使用并查集判定无解。

参考代码

\large{\text{Part2.5 费用流}}

\scriptsize{\text{边加上了费用，网络流也变得更强大了。}}

\texttt{Part2.5.1 有负环的费用流}

P7173 有负环的费用流

一般我们会使用最短增广路算法求解费用流，但是如果图中出现了负权圈的情况的时候，最短增广路算法的数学归纳法基础将会失效，算法将会给出错误的答案甚至出现无法退出的情况。

虽然原图存在负权圈，但显然原图的最小费用最大流仍然存在。根据题目条件，即可以存在一个独立于源汇的增广圈，我们可以通过对所有负权边强制满流达到目的。

考虑增加超级源 s' 和超级汇 t'，对于每条负权边 u \to v，设其容量为 w，费用为 c。将其满流后，可以将其转化为 v \to u 的一条容量为 w，费用为 -c 的边，并加上对费用的贡献。

设 \operatorname{tot}(u) 为 u 附近的所有负权边出边的容量减去所有负权入边的容量。对于 \forall u \in \mathrm V,\,u \ne s',\,u \ne t'，如果 \operatorname{tot}(u) > 0，则从 s' 向 u 连一条容量为 \operatorname{tot}(u)，费用为 0 的边。如果 \operatorname{tot}(u) < 0，则从 u 向 t' 连一条容量为 -\operatorname{tot}(u)，费用为 0 的边。

跑一遍最小费用最大流，可知原图上已不存在负权圈。

再以 s 为源点，t 为汇点，跑一遍最小费用最大流。

答案即为原图的最小费用最大流。

参考代码

\text{Part2.5.2 方格取数问题}

P1004 方格取数

题目大意：给定一张 n \times n 的网格图，每个结点有权值，要求找出两条从 (1,\,1) 到 (n,\,n) 的路径，使得经过的结点权值之和最大，每个结点允许经过多次，但相同结点的权值只能计算一次。

我们应该很快就能看出这道题的 dp 做法，并且本题的 dp 做法也确实是最优做法，但其实这道题也可以用费用流迅速切掉。

经过多种建模的历练，本题的建模方式应该很显然，假设当前结点所填数为 w。

首先很显然的拆点，然后从 s 向结点 (1,\,1) 的入点连容量为 2，费用为 0 的边，从 (n,\,n) 的出点向 t 连一条容量为 +\infty，费用为 0 的边。然后每个方格内结点的入点向出点连容量为 1，费用为 -w 的边。因为每个结点能经过多次，但数只能被取一次，接着从每个方格内结点的入点向出点连容量为 +\infty，费用为 0 的边。最后方格内结点按题目要求类似连容量为 +\infty，费用为 0 的边。

最后跑费用流，\mathrm{mincost} 的相反数即为答案。

参考代码

为什么这道题我们要用费用流来做呢？接下来看一道几乎一样的题。

P2045 方格取数加强版

题目大意：给定一张 n \times n 的网格图，每个结点有权值，要求找出 k 条从 (1,\,1) 到 (n,\,n) 的路径，使得经过的结点权值之和最大，每个结点允许经过多次，但相同结点的权值只能计算一次。

这道题与上一道题几乎是同一样的题，但是这道题我们发现如果使用 dp，不管是时间还是码量上都会爆炸，但是我们神奇的发现相同的费用流写法却能轻松应对，这就体现了网络流可扩展性高的特点。

这次我们只需要将 s 连向 (1,\,1) 的边的容量改为 k，然后其他连边不变，就能直接通过此题。

参考代码

\text{Part2.5.3 区间模型}

P3358 最长k可重区间集问题

题目大意：给定多个开区间和一个数字 k，要求从中选出多个区间，使得任何一个数 x 被覆盖的次数不大于 k，且被选出的区间总长度和最大，求最大长度。

如果觉得初看并不像费用流，那就再往费用流方面仔细想想。

因为流具有传递性，我们可以考虑从 $s$ 到结点 $1$ 连容量为 $k$，费用为 $0$ 的边，每个结点依次向后一个结点连容量为 $k$，费用为 $0$ 的边，一直到末端结点，此时向 $t$ 连容量为 $k$，费用为 $0$ 的边。为什么呢？很容易想到，没有结点被 $k$ 覆盖且还有剩余区间的方案一点是严格不优的，因为这个时候我们显然可以再加一个区间，又因为区间的长度严格非负，所以该方案严格不优。因此最优方案只能从结点完全被覆盖的地方找，而我们可以证明该图上的最大流严格为 $k$。接着每次读入一个闭区间 $[l_i,\,r_i]$，我们从 $l_i$ 向 $r_i$ 连容量为 $1$，费用为 $r_i-l_i$ 的边。 ![](https://cdn.luogu.com.cn/upload/image_hosting/rbvth81w.png) 观察算法流程，因为只有加边，且 $s$ 到结点 $1$ 的容量只有 $k$，所以该图上最大流严格为 $k$。每个区间只可能被用一次，每次增广如果经过一个区间只可能会增广 $1$ 的流量，否则没有新的区间可用，算法经过这一轮增广后结束。因为费用流的正确性，我们取到的区间集一定是最优的。本题需要离散化，限于篇幅，不再讲述。 [参考代码](https://www.luogu.com.cn/paste/5qxsxp7s) $\text{Part2.5.4 后效性模型}

后效性模型是指当前时刻的决策会影响之后的状态的一种费用流模型。

P1251 餐巾计划问题

题目大意：

总共有 \mathrm N 天，每天需要 r_i 个干净餐巾。可以购买新的餐巾,每块餐巾的费用为 p，或者把旧餐巾送到快洗部，洗一块需 m 天，其费用为 f。或者送到慢洗部,洗一块需 n 天，其费用为 s。要求找出最优方案，使得每一天的需求被满足，在此前提下使得总费用最小，求出总费用。

首先，建立时间轴，我们每一天都要使用干净餐巾，又会制造脏餐巾，所以我们将一天 d_i 拆成两个点 d_i' 和 d_i''，可以对应看做早上和晚上，每一天早上我们会收到干净餐巾，每一天晚上我们会向后发送脏餐巾。

为什么要拆点？因为我们要处理干净餐巾被消耗成为脏餐巾的过程，在求解过程中，如果不拆点，流将会流向不合法的地方，导致答案错误。

然后，每一个 d_i'' 都向 d_{i+1}' 连容量为 r_i，费用为 0 的边，代表每一天早上可以接受上一天晚上的脏餐巾，与题意相符。

其次，每个 d_i' 都要向 t 连一条容量为 r_i，费用为 0 的边，表示每一天的需求 r_i。

再其次，我们从每一个 d_i'' 向 d_{i+1}'' 连容量为 +\infty，费用为 0 的边，代表可以将当天的脏餐巾预留给下一天晚上。

接着，我们处理购买餐巾的情况，从 s 向每一个 d_i' 连容量为 +\infty，费用为 p 的边，代表购买餐巾，要花费 p 元。

再然后，我们从每个 d_i' 向 d_{i + m}'' 连容量为 +\infty，费用为 f 的边，代表送到快洗店。

同理，我们从每个 d_i' 向 d_{i + n}'' 连容量为 +\infty，费用为 s 的边，代表送到慢洗店。

跑最小费用最大流，费用即为答案。

参考代码

可以看到，后效性模型的根本就是建立时间轴，找到改变后续状态的结点，对该结点进行操作。 时间一定是重要元素，只有出现时刻变化且当前操作影响后续结点的时候才能建立时间轴，进而对后续结点进行求解。

\text{Part2.5.5 求最短/长往返路}

最后，用一个小小的内容结束本章。

P2770 航空路线问题

题目大意：给定一张 n 个结点的图，求出一条起始点都为结点 1 的回路，使得经过的结点数最多，初始只能从编号低的结点走到编号高的结点，如果编号最高的结点后就只能从编号高的结点走向编号低的结点，求最优方案并输出，其中每个结点都只能经过一次。

首先，每个结点只能经过一次，所以拆点。将点 u 拆为 u' 和 u''，从 u' 向 u'' 连容量为 1，费用为 0 的边，代表经过这个点。不同的是结点 1 和结点 n 的入点需要向出点连容量为 2，费用为 0 的边，因为两者要经过两次。

接下来就是处理连边，对于每个连边，都连容量为 1，费用为 -1 的边。

判定无解的话直接检查 \mathrm{maxflow} 是否等于 2 即可，但是如果只有两个点且能从 1 直接到达 n 的时候就需要特判一下，输出方案建议使用两次 dfs 查找路径。

参考代码

\large{\text{Part2.6 最大权闭合子图}}

定义：

闭合子图：对于一个有向图 \mathrm {G = \langle V,\,E \rangle}，存在点集合 \mathrm S，任取点 u \in {\mathrm S}，u 的出边的另一个点也属于 \mathrm S ，则为闭合图。

最大权闭合子图：\forall u \in \mathrm {V}，都有一个权值函数 \operatorname{w}(u)，如果存在一个点集 {\mathrm S \subseteq \mathrm G}，使得 \sum_{u \in {\mathrm S}}\operatorname{w}(u) 最大，则称 \mathrm S 为 \mathrm G 的最大权合子图。

P2762 太空飞行计划问题

题目大意：有 m 个实验和 n 个仪器，做完每个实验都能获得一定的钱，但是每个实验又需要一些仪器，而购买这些仪器又需要一定的钱，试求出最优方案，使得最终所得钱数最大。

转化一下题意，实验的点权为正，仪器的点权为负，选择了一个实验必须选择其所要用的仪器。

即求出原图的最大权闭合子图。

建模方法如下：

从超级源点 s 向所有正权点连容量为点权的边。
从所有负权点向超级汇点 t 连容量为点权的相反数的边。
最后，原图中的结点正常连边，容量为 +\infty。
跑最小割，所有正权点的和减去最小割即为最大权闭合子图的总点权。

证明：

引理 1： 最小割一定是简单割，证明显然，略去。

引理 2： 简单割一定与一个闭合图对应。

证明引理 2：

闭合子图是简单割：考虑反证法，闭合子图如果不是简单割，则存在一条边 (u,\,v)，使得 u \in {\mathrm S},\,v \in {\mathrm T}，且 \operatorname{f}(u,\,v) = +\infty。说明 u 的后续结点不是 v，矛盾。
简单割是一个闭合子图：对于 \forall u \in {\mathrm S}，u 的任意一条出边 u \to v 的容量都是 +\infty 的，因此不可能在最小割集内，因此 v \in {\mathrm S}。故简单割是一个闭合子图。

引理 2 得证。

接下来证明最小割就是最大权的闭合子图。

由最小割的定义，该图上的最小割容量 c 为 \mathrm S 中所有负权点的相反数之和加上 \mathrm T 中所有正权点之和。
由闭合子图的定义，该图上的闭合子图权值 w 为 \mathrm S 中所有正权点之和加上 \mathrm S 中所有负权点之和。
则有 w + c 等于所有正权点之和。
由于图中所有正权点之和为常量，所以 c 越小，w 对应越大，又因为最小割的容量 c 最小，故图中所有正权点之和减去最小割的容量就等于最大闭合子图的容量。

\text{Q.E.D.}

参考代码

\large{\text{Part2.7 最大密度子图}}

定义：在图 \mathrm G = \langle \mathrm{V,\,E} \rangle 中找出一个闭合子图 \mathrm{ G' = \langle V',\,E' \rangle}，使得 \frac{|\mathrm E'|}{|\mathrm V'|} 最大化，则称闭合子图 \mathrm G' 为图 \mathrm G 的最大密度子图。

一般情况下，我们使用01分数规划解决最大密度子图问题。

UVA1389 Hard Life

最大密度子图模板题。

设 g 为最大密度，求这个式子的最大值，我们先得到 \frac{|\mathrm E'|}{|\mathrm V'|} \le g，化解得到 |\mathrm E|-g \times |\mathrm V| \le 0，我们的问题就变成最大化这个式子的值，显然使用二分答案。

对此，我们可以使用两种方法求出该式的最大值。

首先，两种方法的本质都是二分答案密度 g，区别是使用的点数和边数不同，方法二相对更优于方法一。

假设点数为 n，边数为 m，当前二分到的密度为 g，结点 i 的度数为 \operatorname{d}(i)。

将边看做点，转化为最大权闭合子图。普通点的点权为 -g，将其余边建成点，边化成的点的点权为 1，然后向两个端点连容量为 +\infty 的边，每次迭代后重新建图跑最大权闭合子图，二分结束后 s 能走到的点即为最大密度子图。
从 s 向每一个结点连容量为 m 的边，原图内的边容量建为 1，每个结点 i 向 t 连容量为 m + 2g - \operatorname{d}(i) 的边，其余与方法一相同。

对于方案一，因为实践中运用较少，因此不做证明，接下来我们将对方案二进行时空复杂度和正确性上的分析。

正确性证明：

假设 \mathrm{V_1} 为当前子图，\mathrm{V_2} 为 \complement_{\mathrm V}{\mathrm V_1}。

首先，观察公式 |\mathrm E|-g \times |\mathrm V| \le 0，我们的目标显然是最大化该式子的值。可以将其转化为求 g \times |\mathrm V| - |\mathrm E| \ge 0 的最小值，|\mathrm V| 的值相对容易得到，重点是得到 |\mathrm E| 的值。观察边的性质，我们可以将一条边分解为两个点，此时子图中的边数 |\mathrm E|=\frac{\sum_{u \in \mathrm V_1}\operatorname{d}(u)-\mathrm{C[V_1,\,V_2]}}{2}。

其中 \operatorname{d}(u) 表示结点 u 的度数，\mathrm{C[V_1,\,V_2]} 表示 \mathrm V_1 与 \mathrm V_2 之间之间直接相连的边数。

原式变为：

\begin{aligned} & g \times |\mathrm V| - \frac{\sum_{u \in \mathrm V_1}\operatorname{d}(u)-\mathrm{C[V_1,\,V_2]}}{2} \ge 0 &(1.4.1)\\ & = \frac{1}{2}\left(2g \times |\mathrm V| - \left(\sum_{u \in \mathrm V_1}\operatorname{d}(u)-\mathrm{C[V_1,\,V_2]}\right)\right) \ge 0&(1.4.2)\\ & = \frac{1}{2}\left(\sum_{u \in \mathrm V_1}{(2g - \operatorname{d}(u)})+\mathrm{C[V_1,\,V_2]}\right) &(1.4.3) \end{aligned}

对此，我们应当对 2g - \operatorname{d}(u) 加上一个较大的数，使得该值为正，显然 \operatorname{d}(u) \le m，因此将 m 作为这个较大的数。

接下来，我们将证明最小割就是原式的最大值。

我们可以将原图分为两个集合 \mathrm S=\mathrm V_1 \cup \{s\},\;\mathrm T = \mathrm V_2 \cup \{t\}。

此时任意割集下的连边分四种情况：

将上述连边的贡献累加，得到：

\begin{aligned} & \mathrm{C[V_1,\,V_2]} = n \times m + 2g \times |\mathrm V| - 2|\mathrm E| &(1.5.1)\\ & \frac{n \times m - \mathrm{C[V_1,\,V_2]}}{2}=|\mathrm E| - g \times |\mathrm V| &(1.5.2) \end{aligned}

因此，求得最小割即可得到原式的最大值，而且子图的点集即为 \mathrm S - \{s\}。

时空复杂度证明：

空间复杂度：

点的个数为 n+2： 显然，我们在整个图中只增加了两个点 s 和 t，与原图的结点相加，可得到点的个数为 n + 2，是 \mathcal O(n) 级别的。

边的个数为 2n+m： s \to u 和 u \to t 的这两类边的数量和显然为 2n，u \to v 则是原图的结点，数量为 m，二者加起来即为 2n + m，总边数是 \mathcal O(n+m) 级别的。

因此，方案二的空间复杂度为线性。

时间复杂度：

密度的上限为 m，下限为 \frac{1}{n^2}，二分 g 的时间复杂度显然是 \mathcal O(\log m) 的。因为图中点数和边数都是线性的，故最小割的时间复杂度不变，如果使用 Dinic/ISAP 算法，最小割的时间复杂度为 \mathcal O(n^2m)。与上式相乘得最终时间复杂度为 \mathcal O(n^2m \log m)。

\text{Q.E.D.}

参考代码使用方法二实现，代码自行理解。

参考代码

\large{\text{Part2.8 上下界网络流}}

\scriptsize{\text{有下界约束的网络流即为上下界网络流。}}

设 \operatorname{l}(u,\,v) 为 u \to v 的下界函数，特别的，当 u \to v \notin {\mathrm E} 时，\operatorname{l}(u,\,v) = 0。

定义图 \mathrm G = \langle \mathrm {V,\,E} \rangle 上的流函数 \operatorname{f} : \mathrm {V \times V} \to \mathbb R，满足如下限制：

容量限制： 对于 \forall u,\,v \in {\mathrm V} 有 \operatorname{l}(u,\,v) \le \operatorname{f}(u,\,v) \le \operatorname{c}(u,\,v)。
流量守恒： 对于 \forall u \in {\mathrm{V}}-\{s,\,t\}，要求：

\begin{aligned} & \sum_{v \in {\mathrm{V}}}\operatorname{f}(u,\,v)=\sum_{v \in {\mathrm{V}}}\operatorname{f}(v,\,u) &(1.7.1) \end{aligned}

则称非负值 \operatorname{f}(u,\,v) 为图 \mathrm {G = \langle V,\,E \rangle} 的一个可行流。

一个流的流值 |f| 定义如下：

\begin{aligned} & |f| = \sum_{v \in {\mathrm{V}}}\operatorname{f}(s,\,v)-\sum_{v \in {\mathrm{V}}}\operatorname{f}(v,\,s) &(1.7.2) \end{aligned}

有源汇上下界最大流问题： 给定一个特殊点 s 和一个特殊点 t，找出从 s 到 t 的一个流 \operatorname{f}(s,\,t)，使得 |f| 的值最大。

P5192 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

这道题明显与我们之前做过的所有题都不一样，流量开始有了下界，必须流满下界才行，我们需要一步步将其解决。

\small{\text{Part2.8.1 无源汇上下界可行流}}

顾名思义，无源汇上下界可行流就是没有源汇的情况下，求出图 \mathrm G = \langle \mathrm{V,\,E} \rangle 的一个可行流。

对于每条边，我们可以用上界减去下界得到差值网络，与原网络对应，图中形如 u 的结点就是原网络的结点，形如 u' 的结点就是差值网络的结点。

我们可以对差值网络直接操作得到原网络的可行流。

建模方法如下：

计算每个结点 u 在下界网络的的流入量 \operatorname{in}(u) 和流出量 \operatorname{out}(u)。\operatorname{in}(u) 为 u 的所有入边的容量的总和，\operatorname{out}(u) 为 u 的所有出边的容量的总和。
计算 w = \operatorname{in}(u)-\operatorname{out}(u)。
如果 w > 0，则从超级源点 s' 向 u 连一条容量为 w 的边。如果 w <0，则从 u 向超级汇点 t' 练容量为 -w 的边。
跑最大流，如果存在附加边没满流，则不存在可行流，否则 \mathrm maxflow 加上所有边的下界的和即为可行流的流值。

很容易证明算法的正确性，添加附加边维护了平衡条件，加上下界网络就相当于得到了一个流量平衡的残余网络。

\small{\text{Part2.8.2 有源汇上下界可行流}}

即使加上了源结点 s 和汇结点 t，我们仍然能够方便的求解可行流，从 t 向 s 连一条下界为 0，上界为 +\infty 的边，此时问题便被转化成了无源汇上下界可行流，直接求解即可，此时可行流的容量，即为从 t 到 s 的边的容量。

注意，此时原图的源点和汇点已经被处理为普通点，与后来添加的超级源汇是不同的，此时我们将前者表示为为 s 和 t，后者表示为 s' 和 t'，此时可行流的容量，即为从 t 到 s 的附加边的容量。

\small{\text{Part2.8.3 有源汇上下界最大流}}

终于来到正题了，在可行流的基础上，删去所有附加边，然后用原来的源汇求解一次最大流，加上可行流即为答案。

因为如果存在可行流，之前的网络一定是平衡的，当前的网络当然也是平衡的，满足平衡条件，因此是正确的。

其实不需要删去所有附加边，只需要将 t 到 s 的那条附加边删去即可，因为这两个入度为 0 或者出度为 0 的结点是不影响最大流的求解的。

参考代码

\large{\text{Part2.9 隐式图}}

P2765 魔术球问题

题目大意：共有 n 根柱子，现在要在每根柱子上放编号为 1,\,2,\,3\dots 的球，使得同柱子上相邻的球的编号为完全平方数，找出一个最优方案，使得被放上去的球总数最大。

初看很难让人想到网络流，甚至连图论模型都不太明显，我们可以先试着按照题意建边。

对于柱子不好处理，但是这道题的数据很小，我们可以直接枚举点数，动态开点建图。

每次枚举，如果当前结点的编号加上之前某个结点的编号是完全平方数，则后者向前者连边，求解最优方案下使用的柱子数，一直到使用柱子数大于 n 时退出循环。

观察这张图的性质，我们发现这张图一定是一张 DAG，因为每次我们都只向编号比当前结点大的结点连边，再次观察这张图的最小路径覆盖的性质，我们发现该图上的最小路径覆盖就是最优方案。

证明很简单，每个路径覆盖一定是符合要求的，而最小路径覆盖数也就是最小使用的柱子数。

我们也没有必要每次清空图跑最小路径覆盖，在前一张图的基础上继续跑能极大地优化时间复杂度。

参考代码

\text{Part2.10 枚举与二分}

\scriptsize \texttt{有些时候，我们需要使用网络流进行一些对情况的判断，而普通的网络流已经难以满足我们的需求，这个时候就需要结合枚举或二分来解决问题。}

\small \text{Part2.10.1 枚举}

UVA1104 芯片难题 Chips Challenge

上一道 World Final 的题。

题目大意：给定一个 \mathrm N \times \mathrm N 的字符矩阵 \mathrm C，当当前字符为 \texttt{C} 或 \texttt{/} 时则不能填，当当前字符为 \texttt{.} 时则可以填，你需要在里面填入尽量多的 \texttt{W}，满足如下限制：

对 1 \le i \le \mathrm N，要求 \sum^{n}_{j=1} [\mathrm C_{i,\,j}=\texttt{W} \vee \mathrm C_{i,\,j} = \texttt{C}] = \sum^{n}_{j=1} [\mathrm C_{j,\,i}=\texttt{W} \vee \mathrm C_{j,\,i} = \texttt{C}]
给定 \mathrm {A,\,B}，设 m 为 \sum^{n}_{i=1}\sum^{n}_{j=1} [\mathrm C_{i,\,j}=\texttt{W} \vee \mathrm C_{i,\,j} = \texttt{C}]，则要求 \left(\frac{\sum^{n}_{j=1} [\mathrm C_{i,\,j}=\texttt{W} \vee \mathrm C_{i,\,j} = \texttt{C}]}{m} \le \mathrm{\frac{A}{B}}\right) \wedge \left(\frac{\sum^{n}_{j=1} [\mathrm C_{i,\,j}=\texttt{W} \vee \mathrm C_{i,\,j} = \texttt{C}]}{m} \le \mathrm{\frac{A}{B}}\right) 恒成立。

求出最多能填入的 \texttt{W} 的个数，多组询问，如果不存在合法方案则输出 impossible。

每一行最多能放入的 \texttt{W} 个数是总个数决定的，这样我们难以维护第二个条件，观察到数据范围极小（\mathrm N \le 40），我们可以考虑枚举行内所能放置的 \texttt{W} 的最大个数 k，方便我们求解。

先解决第一个问题，可不可以将枚举改为二分呢？不可以，因为第一个条件，导致可能存在一种情况，使得当前情况不合法，但再在某处填上一个 \texttt{W} 后又会变得合法，样例的第二个测试数据就是这种情况。

所以，我们枚举 k，然后就可以思考如何将题目的状态表示出来。

考虑将图建成二分图，将行列表示为不同的部分，\mathrm X_i 表示第 i 个行结点，\mathrm Y_i 表示第 i 个列结点，开始连边。

我们显然可以预处理每个行和列可能的最多部件个数 \operatorname{hc}_i 和 \operatorname{lc}_i、整个矩阵可能的部件的最多个数 xp、以及原矩阵的 \texttt{C} 的个数 h。

从 s 到每个 \mathrm X_i 连一条容量为 \operatorname{hc}_i，费用为 0 的边。从 \mathrm X_i 到 \mathrm Y_i 连容量为 k，费用为 0 的边，从 \mathrm Y_i 到 t 连容量为 \operatorname{lc}_i，费用为 0 的边。

然后，枚举每个 i，再枚举每个 j，如果 \mathrm C_{i,\,j} 为“ \texttt{.}”，则从 i 到 j 连接容量为 1，费用为 1 的边，表示多余的部分可以从这条边流走（也就是不在这里放部件）

考虑这样得出的 \mathrm {maxflow}，那就是经过这一轮枚举我们所能求得的最大的部件个数，而 \mathrm{mincost} 则是我们没有放的部件个数。

那求完之后如何判断当前方案是否合法呢？很简单，只需要判断 (\mathrm{maxflow} = xp) \wedge (a \times (\mathrm{maxflow - mincost}) \ge b \times k) 是否为真即可。

前者代表我们是否填满了还可以填上 \texttt{W} 的格子，后者代表我们是否满足了条件二。显然因为流的限制，条件一和二必然被满足，又因为费用流的最优性，我们求得的答案是最优答案。

参考代码

\small \text{Part2.10.2 二分}

P2402 奶牛隐藏

题目大意：给定一张 n 个结点，m 条边的无向带权图，每个结点都有容量和牛的数量，每头牛经过一条边 u \to v 都需要花费 u 到 v 的边权个单位时间，试求一个最优方案，使得每一只牛都可以进入容量未满的结点（也就是躲进牛棚），输出最后一头牛躲进牛棚的时间。

时间我们不好用结点表示，如果暴力将图按时间分层，时空复杂度又太高，难以承受。如果枚举总时间，时间复杂度是 \mathcal O(wn^2m) 的，而原数据下 w \le 10^{15}，也是不可能跑过的。

但是，最大值最小，我们可以联想到二分，可不可以二分呢？对这道题，我们设 \operatorname{d}(i) 为给定最大时间为 i 时，每头牛是否能够躲进牛棚，是则返回 1，不是则返回 0。

定义之后很显然的一点是 \operatorname{d}(i) 单调不减。

单调意味着可以二分最大时间，对于每次二分到的时间 \mathrm {time}，我们以每个结点为中心，只和与当前结点的距离不超过 \mathrm {time} 的结点的连边。 我们使用 Floyd 算法预处理最短路径，然后将每个结点 u 拆为点 u' 和 u''，分别表示牛和牛棚。

从 s 向每个 u' 连容量为 u 的牛的数量的边，从 u'' 向 t 连容量为 u 的容量的边，然后从 u' 向 u'' 连容量为 +\infty 的边。（每头牛可以选择躲进当前所在的牛棚）

最后，枚举每个入点 u'，再枚举每个出点 v''，如果 \operatorname{dist}(u',\,v'') \le \mathrm {time}，则从 u' 向 v'' 连容量为 +\infty 的边。

这样跑出来的最大流，就是以当前时间为最大时间，能够躲进牛棚的牛的数量，然后判断是否与 n 相等，再二分，最后二分到的结果就是最终答案。

参考代码

\text{Part2.11 建模方法总结}

在本节中，我们总结了网络流常用的大部分建模方法，个人认为的重点部分是最小割和费用流。实践中这两个部分涉及到的内容最多、建模方法最杂、题目变化最巧妙，因此对这两个部分介绍最多。

接下来将会讲解几道比较经典的题目，因为题目比较经典，为了更好的对照代码理解，出现的代码将会以行内代码块的形式展示。

\Large{\text{Part3 经典难题}}

\text{Part3.1 P2172 部落战争}

题目传送门

题目大意：给定一张 \mathrm {M \times N} 的网格图，每个点要么可到达，要么不可到达，要求用一些路径覆盖所有可到达的点。其中，每条路径可以从容易可到达的结点出发，但是不能走过已经被覆盖的或者不可到达的结点，且只能以 \mathrm {R \times C} 的路径从上往下走。求最优方案，使得路径数量最小，输出最小路径数。

原题的题意看起来很模糊，但经过题意翻译之后很显然是求最小路径覆盖。

求最小路径覆盖当然要先证明当前图是 DAG。因为每条路径只能从上往下走，所以我们只需要保存从上往下的连边，只有从上往下的路径意味着当前图没有环，因此根据定义，当前图是一个 DAG。

能从每个点出发，所以老套路，建立超级源点 s，向所有网格上的结点连容量为 1 的边。

对于不可到达的结点，我们打上一个标记，然后加边的时候特判一下即可。

建立超级汇点 $t$，从所有网格上的结点向 $t$ 连容量为 $1$ 的边，其余边对比最小路径覆盖类似连边，最小路径覆盖数即为答案。参考代码： ```cpp #include <bits/stdc++.h> using namespace std; #define inf 1000000000000000 #define V 100010 #define E 5000010 typedef long long int ll; struct edge { int to, next; ll capa; }; int cnt = 0, head[V], n, m; edge node[E]; inline void add(int fir, int nxt, ll w) { node[cnt].to = nxt, node[cnt].capa = w, node[cnt].next = head[fir], head[fir] = cnt++; } int s, t, dep[V], gap[V], cur[V]; bool vis[205][205]; queue<int>que; ll sum = 0; inline void initing() { memset(dep, -1, V * sizeof(int)); memcpy(cur, head, (t + 1) * sizeof(int)); } inline void bfs() { int fro, ito; que.push(t); dep[t] = 0; ++gap[dep[t]]; while (!que.empty()) { fro = que.front(); que.pop(); for (register int i = head[fro]; i != -1; i = node[i].next) { ito = node[i].to; if (dep[ito] == -1) { dep[ito] = dep[fro] + 1; que.push(ito); ++gap[dep[ito]]; } } } } ll dfs(int u, ll flow) { if (u == t || flow == 0)return flow; ll used = 0, wei = 0; for (register int i = cur[u]; i != -1; i = node[i].next) { cur[u] = i; if (dep[u] == dep[node[i].to] + 1 && node[i].capa) { wei = dfs(node[i].to, min(flow - used, node[i].capa)); if (wei) { node[i].capa -= wei; node[i ^ 1].capa += wei; used += wei; } } if (used == flow)return used; } --gap[dep[u]]; if (!gap[dep[u]])dep[s] = t + 1; ++gap[++dep[u]]; return used; } int r, c; ll ISAP() { initing(); bfs(); while (dep[s] < t) { sum += dfs(s, inf); memcpy(cur, head, (t + 1) * sizeof(int)); } return sum; } inline int in(int x, int y){ return (x - 1) * m + y; } inline int out(int x, int y){ return in(x, y) + n * m; } inline void addE(int u, int v, ll w){ add(u, v, w); add(v, u, 0); } inline int ok(int x, int y){ return (x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y]); } int main() { ios::sync_with_stdio(0); cin.tie(); cout.tie(); memset(head, -1, V * sizeof(int)); cin >> n >> m >> r >> c; s = 2 * n * m + 1, t = 2 * n * m + 2; char d; int num = 0; int dx[4] = {r, r, c, c}, dy[4] = {c, -c, r, -r}; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> d; if(d == 'x')vis[i][j] = true, ++num; else { addE(s, in(i, j), 1); addE(out(i, j), t, 1); } } } int x, y; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(vis[i][j])continue; for(int k = 0; k < 4; k++){ x = i + dx[k], y = j + dy[k]; if(ok(x, y))addE(in(i, j), out(x, y), 1); } } } cout << n * m - num - ISAP(); return 0; } ``` $\text{Part3.2 P4542 营救皮卡丘}

题目传送门

~~顺道宣传一下自己的题解~~

题目大意：给定一张 n 个结点的图，边有边权，要求用 \mathrm K 个路径覆盖所有结点。只有所有编号小于 \mathrm K 的结点都被覆盖，才能覆盖第 \mathrm K 个结点，每个路径可以在任意被覆盖的点出发或结束，在此前提下找出最优方案，使得所有路径长度之和最小。

如果没有加粗的条件，这道题就是一道裸的最小顶点集覆盖，但是我们发现这个条件很难处理，根本无法用之前学过的建模方法进行建模。

首先，处理比较简单的条件。

建立超级源点 s 和超级汇点 t，从 s 到 0 号结点连容量为 \mathrm K，费用 0 的边，这样使用 \mathrm K 个路径的条件就被处理完了。

每个路径可以在任意被覆盖的点出发或结束，套用 DAG 最小路径覆盖的老套路，从 s 向每个非 0 结点的入点 u' 连容量为 1，费用为 0 的边，每个结点的出点 u'' 向 t 连容量为 1，费用为 0 的边。

接下来就是处理粗体突出的那一个条件了。

换一个描述方法，将这个条件这样描述：当前结点 u 走到另外一个结点 v，只能经过从 u 到 v 且路径上所有结点的编号都不大于 \max\{u,\,v\} 的最短路径。

为什么是最短路径，因为只有最短路径满足最优性。

数据范围较小，我们显然可以使用 \mathcal O(n^3) 的 Floyd 算法预处理每个点对之间满足限制的最短路径，然后按照最短路径长度连边，因为每条边可以经过多次，所以从 u 连向 v 连容量为 +\infty，费用为 \operatorname{dist}(u,\,v) 的边。

对于参考代码，注意如果 \operatorname{dist}(u,\,v) = +\infty，则不能连边。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000000000
#define V 100100
#define E 500100
typedef long long int ll;
struct edge {
    int to, next;
    ll capa, cost;
};
int cnt = 0, head[V], n, m; edge node[E];
inline void add(int fir, int nxt, ll w, ll c) {
    node[cnt].to = nxt,
        node[cnt].capa = w,
        node[cnt].cost = c,
        node[cnt].next = head[fir],
        head[fir] = cnt++;
}
int s, t, cur[V]; deque<int>que; ll dep[V], sum = 0, cost = 0;
bool vis[V];
inline bool spfa() {
    for (register int i = 0; i <= t; ++i)dep[i] = inf;
    dep[s] = 0; que.push_back(s); int u, v;
    while (!que.empty()) {
        v = que.front(); que.pop_front();
        for (register int i = head[v]; i != -1; i = node[i].next) {
            u = node[i].to;
            if (dep[v] + node[i].cost < dep[u] && node[i].capa) {
                dep[u] = dep[v] + node[i].cost;
                if (!que.empty() && dep[u] < dep[que.front()])que.push_front(u);
                else que.push_back(u);
            }
        }
    }
    return (dep[t] != inf);
}
ll dfs(register int v, register ll flow) {
    if (v == t || flow == 0)return flow; ll used = 0, wei = 0;
    vis[v] = true;
    for (register int i = cur[v]; i != -1; i = node[i].next) {
        cur[v] = i;
        if (!vis[node[i].to] && dep[node[i].to] == dep[v] + node[i].cost && node[i].capa) {
            wei = dfs(node[i].to, min(flow - used, node[i].capa));
            if (wei) {
                node[i].capa -= wei,
                    node[i ^ 1].capa += wei,
                    used += wei,
                    cost += node[i].cost * wei;
            }
        }
        if (used == flow)break;
    }
    vis[v] = false;
    return used;
}
inline void Dinic() {
    while (spfa()) {
        memcpy(cur, head, (t + 1) * sizeof(int));
        sum += dfs(s, inf);
    }
}
ll d, dis[205][205];
inline void addE(int u, int v, ll w, ll c) {
    add(u, v, w, c);
    add(v, u, 0, -c);
}
void init() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if(i != j)dis[i][j] = inf;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();
    memset(head, -1, V * sizeof(int));
    cin >> n >> m >> d; ++n;
    int u, v; ll w; s = 2 * n + 1, t = 2 * n + 2;
    addE(s, 1, d, 0);init();
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w; ++u, ++v;
        dis[u][v] = dis[v][u]  = min(dis[u][v], w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (k <= max(i, j))dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    for (int i = 1; i <= n; i++) {
        if(i != 1)addE(s, i, 1, 0);
        addE(i + n, t, 1, 0);
        for (int j = i + 1; j <= n; j++) {
            if (dis[i][j] != inf)addE(i, j + n, inf, dis[i][j]);
        }
    }
    Dinic();
    cout << cost;
    return 0;
}

\text{Part3.3 P4003 无限之环}

~~终于，大 BOSS 来了。~~

题目传送门

题目大意：给定一张 n \times m 的网格图，每个结点可以看作一个水管，每个非直线型水管每次可以旋转 90 度（水管具体形态见题目描述），求出最小旋转次数，使得每个水管的接口都与一个相邻的水管接口相对应。

网络流神题，题意很恶心，几乎没法简化，如果不是算法标签连判断是不是网络流都很难。

不存在漏水的地方，可以抽象为满流，而最小旋转次数，我们可以将其抽象为费用。

首先，考虑简单情况，不考虑旋转次数，判断是否漏水。

考虑染色，我们发现黑白相间染色刚好能够满足我们的需求，将相邻结点分别连源汇，判断是否漏水就很简单了，直接求解最大流，如果不满流则漏水。

但是，这样根本无法得到旋转次数，于是我们考虑用费用当作旋转次数，而这样必须要将流流向正确的位置。

因为不拆点会导致流流向不合法的地方，所以必须要拆点，将一个点拆成上下左右和中间共五个点，上下左右的结点可以看作是插头，分别发出或接受相邻结点的流。

对于旋转，我们使用带费用的边以模拟旋转，显然可以分类讨论。

直线型不能旋转，所以没有带费用的边，十字形没必要旋转，所以也没有带费用的边。

接下来的 12 种情况可以规约为三种本质不同的情况。

\text{Q 型共四种}

我们将形如这个形状的水管称为 Q 型水管。

我们发现如果刚好在接头方向有流流过，则不需要花费费用，如果从当前方向转到对向则需要花费 2 个单位的费用，转到其他方向需要花费 1 个单位的费用。

可以这样连边，其中黄色的边费用为 0。

为什么不直接从中点向四周连边呢？因为这样子会使得结点流出或流入不止 1 个单位的流，显然不满足题意。

这时候我们假设当前结点是黑点，下面正好有一个联通的接头，我们从中点出发，经过上点，然后再通过费用为 2 的边刚好进入下方的接头，完美的模拟了旋转的情况。

其他方向分类讨论即可。

\text{L 型共四种}

我们将形如这个形状的水管称为 L 型水管。

和 Q 型管类似，可以这样连边。

为什么没有费用为 2 的边？因为如果要转两次，两条边都会走过，费用刚好为 2，正好能够模拟旋转的情况，其余情况类似讨论即可。

\text{T 型共四种}

我们将形如这个形状的水管称为 T 型水管。

继续按照老套路连边。

假设只转了一下，那么中点向右点的边一定还存在，然后到左点的路径一定经过左右两条边，所以是上点和下点向左点连费用 1 的边。如果转了两下则右点和左点互换，上下点的连边仍然不改变，所以右点向左点连费用为 2 的边，其余情况类似讨论。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000000000
#define V 100100
#define E 500100
typedef long long int ll;
struct edge {
    int to, next;
    ll capa, cost;
};
int cnt = 0, head[V], n, m; edge node[E];
inline void add(int fir, int nxt, ll w, ll c) {
    node[cnt].to = nxt,
        node[cnt].capa = w,
        node[cnt].cost = c,
        node[cnt].next = head[fir],
        head[fir] = cnt++;
}
int s, t, cur[V]; deque<int>que; ll dep[V], sum = 0, cost = 0, rsum = 0;
bool vis[V];
inline bool spfa() {
    for (register int i = 0; i <= t; ++i)dep[i] = inf;
    dep[s] = 0; que.push_back(s); int u, v;
    while (!que.empty()) {
        v = que.front(); que.pop_front();
        for (register int i = head[v]; i != -1; i = node[i].next) {
            u = node[i].to;
            if (dep[v] + node[i].cost < dep[u] && node[i].capa) {
                dep[u] = dep[v] + node[i].cost;
                if (!que.empty() && dep[u] < dep[que.front()])que.push_front(u);
                else que.push_back(u);
            }
        }
    }
    return (dep[t] != inf);
}
ll dfs(register int v, register ll flow) {
    if (v == t || flow == 0)return flow; ll used = 0, wei = 0;
    vis[v] = true;
    for (register int i = cur[v]; i != -1; i = node[i].next) {
        cur[v] = i;
        if (!vis[node[i].to] && dep[node[i].to] == dep[v] + node[i].cost && node[i].capa) {
            wei = dfs(node[i].to, min(flow - used, node[i].capa));
            if (wei) {
                node[i].capa -= wei,
                    node[i ^ 1].capa += wei,
                    used += wei,
                    cost += node[i].cost * wei;
            }
        }
        if (used == flow)break;
    }
    vis[v] = false;
    return used;
}
inline void Dinic() {
    while (spfa()) {
        memcpy(cur, head, (t + 1) * sizeof(int));
        sum += dfs(s, inf);
    }
}
inline void addE(int u, int v, ll w, ll c, bool col = true) {
    if (!col)swap(u, v);
    add(u, v, w, c);
    add(v, u, 0, -c);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();
    memset(head, -1, V * sizeof(int));
    cin >> n >> m; s = n * m * 5 + 1, t = n * m * 5 + 2;
    int v, dir = n * m; ll w; bool col;//黑为 true,白为 false
    //dir = n*m,dir*1 上,dir*2 右,dir*3 下,dir*4 左
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w; v = (i - 1) * m + j;
            if (w == 0)continue;
            if (col = !(i + j & 1))addE(s, v, inf, 0);
            else addE(v, t, inf, 0);
            if (w & 1)addE(v, v + dir, 1, 0, col),++rsum;
            if (w & 2)addE(v, v + dir * 2, 1, 0, col),++rsum;
            if (w & 4)addE(v, v + dir * 3, 1, 0, col),++rsum;
            if (w & 8)addE(v, v + dir * 4, 1, 0, col),++rsum;
            if (col) {
                if (i - 1)addE(v + dir, v - m + dir * 3, 1, 0);//上
                if (j - 1)addE(v + dir * 4, v - 1 + dir * 2, 1, 0);//左
                if (i + 1 <= n)addE(v + dir * 3, v + m + dir, 1, 0);//下
                if (j + 1 <= m)addE(v + dir * 2, v + 1 + dir * 4, 1, 0);//右
            }
            switch (w) {
            case 1: {//0001,上有接头
                addE(v + dir, v + dir * 4, 1, 1, col);
                addE(v + dir, v + dir * 2, 1, 1, col);
                addE(v + dir, v + dir * 3, 1, 2, col);
                break;
            }
            case 2: {//0010,右有接头
                addE(v + dir * 2, v + dir, 1, 1, col);
                addE(v + dir * 2, v + dir * 3, 1, 1, col);
                addE(v + dir * 2, v + dir * 4, 1, 2, col);
                break;
            }
            case 3: {//0011,上右有接头
                addE(v + dir, v + dir * 3, 1, 1, col);//上连下
                addE(v + dir * 2, v + dir * 4, 1, 1, col);//右连左
                break;
            }
            case 4: {//0100,下有接头
                addE(v + dir * 3, v + dir * 2, 1, 1, col);
                addE(v + dir * 3, v + dir * 4, 1, 1, col);
                addE(v + dir * 3, v + dir, 1, 2, col);
                break;
            }
            case 5: {//0101,上下有接头
                if (i - 1)addE(v + dir, v - m + dir * 3, 1, 0, col);
                if (i + 1 <= n)addE(v + dir * 4, v + m + dir, 1, 0, col);
                break;
            }
            case 6: {//0110,下右有接头
                addE(v + dir * 3, v + dir, 1, 1, col);//下连上
                addE(v + dir * 2, v + dir * 4, 1, 1, col);//右连左
                break;
            }
            case 7: {//0111,上下右有接头
                addE(v + dir, v + dir * 4, 1, 1, col);
                addE(v + dir * 3, v + dir * 4, 1, 1, col);
                addE(v + dir * 2, v + dir * 4, 1, 2, col);
                break;
            }
            case 8: {//1000,左有接头
                addE(v + dir * 4, v + dir, 1, 1, col);
                addE(v + dir * 4, v + dir * 3, 1, 1, col);
                addE(v + dir * 4, v + dir * 2, 1, 2, col);
                break;
            }
            case 9: {//1001,上左有接头
                addE(v + dir * 4, v + dir * 2, 1, 1, col);
                addE(v + dir, v + dir * 3, 1, 1, col);
                break;
            }
            case 10: {//1010,左右有接头
                if (j - 1)addE(v + dir * 4, v - 1 + dir * 2, 1, 0, col);
                if (j + 1 <= m)addE(v + dir * 2, v + 1 + dir * 4, 1, 0, col);
                break;
            }
            case 11: {//1011,左右上有接头
                addE(v + dir * 4, v + dir * 3, 1, 1, col);
                addE(v + dir * 2, v + dir * 3, 1, 1, col);
                addE(v + dir, v + dir * 3, 1, 2, col);
                break;
            }
            case 12: {//1100,下左有接头
                addE(v + dir * 3, v + dir, 1, 1, col);
                addE(v + dir * 4, v + dir * 2, 1, 1, col);
                break;
            }
            case 13: {//1101,上下左有接头
                addE(v + dir, v + dir * 2, 1, 1, col);
                addE(v + dir * 3, v + dir * 2, 1, 1, col);
                addE(v + dir * 4, v + dir * 2, 1, 2, col);
                break;
            }
            case 14: {//1110,下左右有接头
                addE(v + dir * 4, v + dir, 1, 1, col);
                addE(v + dir * 2, v + dir, 1, 1, col);
                addE(v + dir * 3, v + dir, 1, 2, col);
                break;
            }
            case 15: break;
            }
        }
    }
    Dinic();
    if (sum * 2 != rsum)cout << "-1";
    else cout << cost;
    return 0;
}

\Large{\text{Part4 后记}}

本日报于 2022 年 5 月 18 日中午正式开始写，至 2022 年 5 月 30 日下午完成，共历 12 天，总字数在 47k 左右。只讲这么点不是因为网络流只有这一点内容，而是因为学校机房的电脑配置太好，编辑到 20k 的时候就开始卡，越到后面越难受，于是强行将内容压缩成了 47k。

之后可能随时会更新，仅以此日报祭 OI 生涯的第一年。

完结撒花~

\large{\text{Part5 参考文献}}

网络流的建模方法总结

算法学习笔记(60): 上下界网络流

平面图上最小割=对偶图最短路

最大权闭合子图

最大密度子图

\large{\text{Part6 Updata}}

\small\text{2022.6.20 20PM}

由于评论区 @清烛 dalao 的意见，会在 6 月 23 号之前补充最小割的定义和证明，感谢他的建议。

\small\text{2022.6.28 16PM}

增加 「二分图最小顶点集覆盖」 相关证明，现在已经 53k 了。

\small\text{2022.8.9 10AM}

优化了对偶图最短路相关的内容，55k 了。

\small\text{2022.8.12 21PM}

一次大修，优化了最小割方面的证明，优化了 \LaTeX。

\small\text{2022.8.13 22PM}

丰富了 \text{Part2.2} 最小割相关内容。

\small\text{2022.8.13 23PM}

肝完了最大密度子图的证明，同时修了一下无限之环的第一个图的祸。

\small\text{2022.8.15 23PM}

更新了枚举与二分套网络流的相关内容。

\small\text{2022.8.17 15PM}

响应你谷号召将标题的 \texttt 改成了 \text，优化了 \LaTeX。

\small\text{2023.1.27 17PM}

根据评论区 @fjy666 的建议，增加了附属题单，感谢 ta 的贡献。

\small\text{2023.1.28 11PM}

修改了 @Bring 提出的关于题目芯片难题处公式的错误，感谢 ta 的贡献（至于其他的等有空了再修，咕咕咕）

\large{\text{Part7 Target}}

这里是更新目标区。

扩充分层图相关的内容。（未完）
扩充最小路径覆盖相关内容，改名为 路径覆盖与链覆盖，主要增加 「最小链覆盖」 和 「最长反链」 以及 「\mathrm{Dilworth} 定理」 相关内容。（已做完）

注意，由于本人过于蒟蒻，\mathrm{Dilworth} 定理的证明还没有写完，同时也要准备 NOIP，所以目前只能增加到这里，见谅。（想看证明的可以看导弹拦截里第八篇题解的链接 link）

增加 「混合图上欧拉路径」 相关内容。（未完）
扩充费用流区间模型相关的内容。（未完）
极大扩充枚举与二分相关的内容。（未完）
增加 「优化建图」 相关内容。（未完）
增加 「最小乘积模型」 相关内容。（未完）
做完上述内容后全面美化 \LaTeX。（未完）