题解 - 网络流 24 题

这是个人的 网络流 24 题 做题记录。

1. 飞行员配对方案问题

类型：最大流（二分图）。

题面

一共有 $n$ 个飞行员，其中有 $m$ 个外籍飞行员和 $(n - m)$ 个英国飞行员，外籍飞行员从 $1$ 到 $m$ 编号，英国飞行员从 $m + 1$ 到 $n$ 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

解法

二分图最大匹配一眼题。

2. 方格取数问题

类型：最大流（最小割）。

题面

有一个 $m$ 行 $n$ 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

解法

没有公共边 $\rightarrow$ 割。

所以就按照棋盘的二分图染色，跑这个图的最小割。总和 $-$ 最小割 $=$ 最大和。

总有指定一种颜色连向另一颜色。其中每个点与源/汇的容量是这个点的值，而两个颜色中间的连边为 INF，表示不作限制，在左右两种颜色之中取最优。

3. 最长不下降子序列问题

类型：最大流

题面

给定正整数序列 $x_1 \ldots, x_n$。

1. 计算其最长不下降子序列的长度 $s$。
2. 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。
3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为 $s$ 的不下降子序列。

令 $a_1, a_2, \ldots, a_s$ 为构造 $S$ 时所使用的下标，$b_1, b_2, \ldots, b_s$ 为构造 $T$ 时所使用的下标。且 $\forall i \in [1,s-1]$，都有 $a_i \lt a_{i+1}$，$b_i \lt b_{i+1}$。则 $S$ 和 $T$ 不同，当且仅当 $\exists i \in [1,s]$，使得 $a_i \neq b_i$。

解法

第一问，是朴素的 DP，$O(n^2)$。

第二问，做一个转化：序列 $=$ 路径，或者说，前驱-后继 $=$ 边。意思是说，把前后可能在序列里并列的两个元素连一条边，流就会经过这个路径。

再加一个拆点限流技巧，保证每个点只有一次。

再假设每个序列虚的头元素为 $S$，虚的尾元素为 $T$，最大流即可。

第三问，取消 $x_1$ 和 $x_n$ 的流量限制即可。

4. 圆桌问题

类型：最大流（二分图）。

题面

有来自 $m$ 个不同单位的代表参加一次国际会议。第 $i$ 个单位派出了 $r_i$ 个代表。

会议的餐厅共有 $n$ 张餐桌，第 $i$ 张餐桌可容纳 $c_i$ 个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

解法

就是说，从源点连出每个单位，再将每个餐桌连向汇点，如果源点出来的每个流都能到汇点就有方案。

从源点连出一部分点，将一部分点连向汇点，这两部分点又有其他的连边，这是一个常形——二分图。

因为一个单位每个人都要在不同的餐桌，所以一个单位向每个餐桌连一条容量为 $1$ 的边。跑个最大流即可。

5. 试题库问题

类型：最大流（二分图）。

题面

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

解法

与上一题基本一致，只是左边每个试题（单位）连向右边每个餐桌（卷子）的边是给定的，不是全都连。

6. 魔术球问题

类型：最大流（二分图）。

题面

假设有 $n$ 根柱子，现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1$，$2$，$3$，…的球：

1. 每次只能在某根柱子的最上面放球。

2. 同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球。例如，在 $4$ 根柱子上最多可放 $11$ 个球。

对于给定的 $n$，计算在 $n$ 根柱子上最多能放多少个球。

解法

依然用二分图最大匹配模型。左部只向右部连出边，表示一堆关系的前驱；右部只从左部连入边，表示一对关系的后继。

前驱-后继 $=$ 边，枚举每个完全平方数连边。

此时，最大流就是最小割，也就是 最大匹配数 $=$ 总数 $-$ 最小柱子数。

所以，我们一个一个加点，看一看何时的最小柱子数超过 $n$ 然后输出即可。

归纳：题型

1. 最大流-二分图，可以使用二分图表示匹配/选择，例：圆桌问题；
2. 最大流-最小割，用割表示当前元素存在某种独立关系，例：方格取数问题；
3. 最大流，使用路径表示序列，例：最长不下降子序列问题。

归纳：技巧

1. 棋盘使用二分图染色，例：方格取数问题；
2. 对于序列并行/序列数目最大化，用源点表示虚的头结点，用汇点表示虚的尾结点，例：最长不下降子序列问题；
3. 一个点可以拆成两个点，其中间连边，表示这个点的最大流量，即拆点限流，例：最长不下降子序列问题；
4. 特殊容量 $1$，表示一个路径，可用于计数，例：试题库问题；
5. 特殊容量 INF，表示不作限制/自然选择最优，例：方格取数问题；
6. 表示序列，用路径表示，例：最长不下降子序列问题；
7. 表示前驱-后继关系，用连边（容量常为 $1$）表示，例：魔术球问题。