网络流中相关习题总结2

上上篇 基础知识

上一篇 习题总结1

记号：

1. 在提及两端点情况下，用 $(c, w)$ 表示一条容量为 $c$ ，费用为 $w$ 的边，下同。

2. 用 $u \rarr v, (c, w)$ 来表示从 $u$ 向 $v$ 连一条容量为 $c$ ，费用为 $w$ 的边，下同， $c$ 有时会省略。

类型4：最小割

最小割主要解决的是这样的问题：求满足某种条件（要转化为源点和汇点不联通）的最小代价。

一个小模型

这里有个能在部分题中用上的模型：

有若干个东西，每个东西都有一些价值。

还有若干个限制，对于每个限制，有若干个物品不能同时选（即必须有至少一个不选，通常为两到三个）。

那么把每个物品拆点，连边容量为价值。

然后对于每个限制，用边从源点到汇点串起来（边权 $\infty$ ，可能要安排顺序，形成环的话很麻烦），求最小割，答案就是总价值减去最小割。

解释：每个限制体现在图中都是一些路径，而这中的每条路径都要割断一些点，让源点和汇点不联通，用网络流完成最优的决策，即删除的点代价最小。

P2774 方格取数问题

https://www.luogu.com.cn/problem/P2774

给定一个网格图，从网格中选取若干个数，使选取的格子没有公共边，求取出的数最大的和。

相邻的两个格子不能同时取，显然就是上面的模型了，黑白染色一下，然后源点连黑的，容量为格子中的数字，然后黑点连相邻的白的，容量 $\infty$ ，白的连汇点，容量为格子中的数字。

P3355 骑士共存问题

https://www.luogu.com.cn/problem/P3355

在一张 $n\times n$ 的方格国际象棋棋盘上，马可以攻击的范围如下图所示：

有些格子设置了障碍，不能进入，求最多放置多少匹马，使它们互相不攻击。

黑白染色后，一匹马能攻击到的格子的颜色恰好是和它在的格子颜色相反，并且假如 $A$ 能攻击到 $B$ ，$B$ 也能攻击到 $A$ 。

假如一条点有障碍，在加边的时候忽略它即可。

和上一题差不多。

源点连黑点，黑点连能够攻击到的白点，白点连汇点。

P2762 太空飞行计划问题

https://www.luogu.com.cn/problem/P2762

有 $m$ 个实验，每个实验 $i$ 收益 $p_i$ ，有 $n$ 个仪器，买仪器 $i$ 花费 $c_i$ ，每个实验 $i$ 需要某些仪器 $R_i$ ，仪器可以重复使用，问最大收益，并输出方案。

这题是最大权闭合子图问题，关于这个问题，不过多介绍，考虑用上面提及的模型解决。

发现这题的限制是：选实验 $i$ 和不选仪器 $j \in R_i$ 。

发现「不选」的条件有点特殊，考虑怎么处理。

在模型中，先选上所有的物品，然后减去最小的代价，一个物品的代价就是选它减不选它对答案贡献的差。

实验 $i$ ，不选它贡献为 $0$ ，选它贡献为 $p_i$ 。

不选仪器 $j$ ，不选它贡献为 $-c_j$ ，选它贡献为 $0$ 。

答案为 $\sum p_i - 最小割$

按照上面模型的方法建图，不过由于只有两个限制，不用拆点。

从源点向实验节点 $i$ 连 $p_i$ 的边 ，从仪器节点 $j$ 向汇点连 $c_j$ 的边，从实验节点 $i$ 向所有 $j \in R_i$ 连 $\infty$ 的边，跑最小割，然后用 $\sum p_i$ 减去最小割就是答案。

还要输出方案数：做实验 $i$ ，说明源点到 $i$ 的边没被割，买仪器 $j$ ，说明点 $j$ 到汇点的边被割了。

P4174 最大获利

https://www.luogu.com.cn/problem/P4174

有 $n$ 个基站，每个基站需要 $P_i$ 的成本，有 $m$ 个用户，需要基站 $A_i$ 和 $B_i$ ，可以获利 $C_i$ 。

求最大获利。

和上一题差不多，源点连用户，容量 $C_i$ ，用户 $i$ 连基站 $A_i$ 和 $B_i$ ，边权 $\infty$ ，基站 $i$ 连汇点，容量 $P_i$ 。答案为 $\sum C_i - 最小割$ 。

P5458 水晶

https://www.luogu.com.cn/problem/P5458

地图由若干个密铺的六边形单元组成，如下图所示，为了方便，用 $(x, y, z)$ 表示一个格子，表示从原点开始，按所示的 $x, y, z$ 轴走了 $x, y, z$ 步，注意一个格子可以由多个坐标表示。

有 $n$ 块水晶在地图内，第 $i$ 块的坐标为 $(x_i, y_i, z_i)$ ，每块有 $c_i$ 的价值，注意一格内可能有多块水晶。

满足 $x + y + z = 0 (\bmod 3)$ 的格子内有能量源，有能量源的格子内的水晶的价值多 $10\%$ 。

会形成两种共振：

1. $a$ 共振，如果三块水晶所在的格子排列成一个三角形，会有 $a$ 共振。
   

2. $b$ 共振，如果三块格子所在单元连成一条直线，并且中间的格子有能量源，会有 $b$ 共振。
   

你要破坏一些水晶，使不会有共振，并且留下的水晶价值最大。

由于在平面上，只需要两个坐标就够了，要把格子的坐标转换。

发现往 $z$ 轴走 $1$ 格，可以转化为往 $y$ 轴走 $-1$ 格，往 $x$ 轴走一格。

所以 $(x, y, z)$ 被转化为 $(x - z, y - z)$，并且

$$x + y + z \bmod 3 = x + y + 3z - 2z \bmod 3 = x + y - 2z \bmod3 = x - z + y - z \bmod 3$$

故新旧坐标加起来模 $3$ 不变。

而题目中 $x + y + z \bmod 3 = 0$ 的格子有能量源也提醒了我们可以按 $\bmod 3$ 对格子分类。

考虑什么样的有水晶的格子会形成共振。

不难发现，假如一个模 $3$ 余 $0$ 的有水晶的格子旁边有一个余 $1$ 和余 $2$ 的有水晶的格子，那么会引发共振。

根据上面的模型，我们可以这么建图：

拆点，每个有水晶的格子拆成入点和出点，之间连边容量为水晶的价值。

源点向所有模 $3$ 余 $1$ 的点连边，余 $1$ 向相邻的余 $0$ 的点连边，余 $0$ 向相邻的余 $2$ 的点连边，余 $2$ 向汇点连边，这些边边权均为 $\infty$ 。

然后价值和减去最小割就可以了。

另一个小模型

这个模型可以用在一些需要二选一的问题上。

需要作出 $n$ 个一些二选一的抉择，设为 $A$ 和 $B$ ，每个选 $A$ 或者选 $B$ 都能有一定价值，同时若干个同选 $A$ 或者同选 $B$ 也能有一定价值，问最大价值。

形式化来说：

有 $n$ 个数，记为 $\{x_n\}$ ，$x_i$ 可以为 $1$ 或 $0$ 。

同时有若干个条件，记为 $(S_j, y_j, v_j)$ ，假如对于 $i \in S_j$ 都有 $x_i = y_j$ ，那么可以有 $v_j$ 的价值。

问最大价值。

我们考虑用联通性来表示一个选择。

如 $i$ 与 $s$ 联通，那么选 $A$ ，否则要与 $t$ 联通，选 $B$ 。

我们考虑加上所有的价值，然后删去尽可能小的，满足「二选一」，可以试着用最小割。

对于每个条件，新建一个节点 $Y_j$ ，若 $y_j = 0$ ，从源点向 $Y_j$ 连 $v_j$ 的边，然后对于 $i\in S_j$ ，从 $j$ 向 $i$ 连 $\infty$ 的边；若 $y_i = 1$ ，反过来即可，即 $i \rarr j \rarr t$ 。

答案就是价值和减最小割。

为什么是正确的呢？

考虑一个点选 $A$ ，那么就要割断所有与 $t$ 的路径。

这样所有要这个点选 $B$ 的条件都不会对答案有贡献了。

P4313 文理分科

https://www.luogu.com.cn/problem/P4313

有一个班级，要文理分科，这个班级可以用 $n \times m$ 的矩阵表示。

对于 $(i, j)$ ：

• 选文科，可以获得 $art_{i, j}$ 的满意值，假如和他相邻的人都选了文科，额外获得 $same\_art{i, j}$ 的满意值。
• 选理科，可以获得 $science_{i, j}$ 的满意值，假如和他相邻的人都选了理科，额外获得 $same\_science_{i, j}$ 的满意值。

问所有人最大满意值之和。

显然就是上面的模型：

对于自己：

$s \rarr (i, j), art_{i, j}$ ， $(i, j) \rarr t, science_{i, j}$ ；

对于周围的人，令 $X_{i, j}, Y_{i, j}$ 是两个为处理 $same\_art$ 和 $same\_science$ 的节点，设 $(i', j')$ 为和 $(i, j)$ 相邻的点。

$s \rarr X_{i, j}, same\_art_{i, j}$ ， $X_{i, j} \rarr (i', j'), \infty$ ， $X_{i, j} \rarr (i, j), \infty$ 。

$Y_{i, j} \rarr t, same\_science_{i, j}$ ， $(i', j') \rarr Y_{i, j}, \infty$ ，$(i, j) \rarr Y_{i, j}, \infty$ 。

P1646 happiness

https://www.luogu.com.cn/problem/P1646

有一个班级，要文理分科，每个人选文科，选理科，相邻的两个人选文科或理科会获得喜悦值，求最大喜悦值之和。

和上面那题几乎一模一样。

源点向每个人连容量为选文科可以获得的喜悦值的边。

对于每对相邻的人，新建一个点，源点向那个点连容量为那对人同时选文科可以获得的喜悦值，然后那个点向那两个人连边。

理科同理，不过反过来。

CF311E Biologist

https://www.luogu.com.cn/problem/CF311E

有一个长度为 $n$ 的 $0/1$ 串 $a$ ，将第 $i$ 个位置变为另一个数字的代价为 $v_i$ 。

然后有 $m$ 个要求，每个要求给定 $k_i$ 个位置（设为 $R_i$ ），要求这些位置同为 $p_i$ ，假如满足，有 $W_i$ 的利润，否则，部分要求要倒给 $g$ 。

求最大收益。

这一题比较不同的地方就是要部分条件要倒给 $g$ 或者 $v_i$，考虑使用 P2762 的方式解决，使得割边时能够把它们剪掉，留着时不计入答案。

建边方式：

若 $a_i = 0$ ， $s \rarr i, 0; i \rarr t, v_i$ ；否则 ， $s \rarr i, v_i; i \rarr t, 0$ 。

对于每一个限制 $j$ ，新建点 $L_j$ ，若 $p_i = 0$ ，$s \rarr L_j, W_i (+ g, \text{假如有要求}); \forall i \in R_j, L_j \rarr i, \infty$ ，若 $p_i = 1$ ， $L_j \rarr t, W_i (+ g, \text{假如有要求}); \forall i \in R_j, i \rarr L_j, \infty$ 。

答案为 $\sum W_i - 最小割$ 。

类型5

这种类型要解决的问题大多可以转化为这样的一个模型：

有一个有向图，求一个子图，满足点 $i$ 的入度不大于 $I_i$ ，出度不大于 $O_i$ ，边数尽可能多，求最小费用或最大收益。

建图方法如下：

对于每个点 $i$ ，拆成两个点 $A_i$ 和 $B_i$ ，然后 $s \rarr A_i, (O_i, 0); B_i \rarr t, (I_i, 0)$ 。如果原图中有一条边 $(u, v, w)$ ，那么连边 $A_u \rarr B_v, (1, w)$ 。

然后跑最小费用最大流。

为什么？

考虑一条边 $(u, v, w)$ 如果被选了，即在网络流中 $(A_u, B_v)$ 流量为 $1$ ，那么 $(S, A_u)$ 的流量会多 $1$ ， $(B_v, t)$ 的流量会多 $1$ 。因为 $(S, A_u)$ 的流量限制为 $O_u$ ，故这里只能连 $O_u$ 条边，满足出度小于等于 $O_u$ 的限制，入度限制同理。

最大流可以保证选至多的边，在很多情况下保证跑满入度或出度，而最小费用保证费用最小。

CF277E Binary Tree on Plane

https://www.luogu.com.cn/problem/CF277E

给定平面上的若干个点，要求组成一棵二叉树，若 $i$ 是 $j$ 的父亲，必须要有 $y_i > y_j$ ，两个点相连的边权定义为两个点之间的欧几里得距离。

求最小二叉树边权和，或报告这样的二叉树不存在。

是上面提及的这个模型，每个点入度小于等于 $1$ ，出度小于等于 $2$ ，每个点向所有 $y$ 比自己小的点连边。

连边方式：

$s \rarr A_i, (0, 2); B_i \rarr t, (1, 0)$ ， $A_i \rarr B_j, y_j \lt y_i, (1, \text{dis}(i, j))$

跑最小费用最大流，假如最大流小于 $n - 1$ 则无解。

P2764 最小路径覆盖问题

https://www.luogu.com.cn/problem/P2764

给定有向图 $G = (V, E)$ ，设 $P$ 是 $G$ 的一个简单路（顶点不相交，特别的，路径长度即所含路径条数可以为 $0$ ）的集合，如果 $V$ 中的每个顶点恰好出现在 $P$ 中的一条路上一次，那么称 $P$ 是 $G$ 的路径覆盖，求最小路径覆盖，即 $|P|$ 最小的 $P$ 。

每个点在一条路径上，说明入度小于等于 $1$ ，出度小于等于 $1$ 。

按照上面的模型建边，得到最多有 $x$ 条边，那么最少要 $n - x$ 条路径，因为 $x$ 个点的入度为 $1$ ，剩下都为 $0$ ，而每个入度为 $0$ 的点都是一条路径的开头。

输出方案也很简单，如果 $A_u \rarr B_v$ 跑满了，说明选 $u \rarr v$ ，得到原图的一个子图，就容易输出了。

P2765 魔术球问题

https://www.luogu.com.cn/problem/P2765

有 $n$ 个柱子，依次向柱子上面放 $1, 2, 3, \cdots$ 的球，要求同一个柱子两个相连的球加起来是一个完全平方数。

把球看成点，把能放在一起的球连起来，需要多少个柱子，就是这个图的最小路径覆盖。

从 $1$ 开始，不断向图中加点，假如加到 $i$ ，找出图中所有 $i$ 能放在上面的点 $j$ ，即 $i + j = x^2, x \in \mathbb{N}$ ，$j$ 向 $i$ 连边，直到这个图的最小路径覆盖大于 $n$ 。

P1251 餐巾计划问题

https://www.luogu.com.cn/problem/P1251

一个餐厅在 $n$ 天中，第 $i$ 天需要 $r_i$ 块餐巾，每天，餐厅可以购买餐巾，每块 $p$ 分，在第 $i$ 天晚上，餐厅可以把旧餐巾送到快洗部，每块 $f$ 分，能在第 $i + m$ 天早上收到餐巾，也可以送到慢洗部，每块 $s$ 分，在第 $i + n$ 天早上收到餐巾。

和我们的模型大抵相符，不过有需要改动的地方，介绍一种采用这种模型思想建图的另一种解释。

把每一天拆成早上和晚上，分别为 $M_i$ 和 $E_i$ 。

$s\rarr E_i, (r_i, 0)$ 表示每天晚上收到 $r_i$ 块脏餐巾。

$M_i \rarr t, (r_i, 0)$ 表示每天早上需要 $r_i$ 块干净餐巾。

$s \rarr M_i, (\infin, p)$ 每天早上可以购买餐巾。

$E_i \rarr E_{i+1}, (r_i, 0)$ 晚上不洗可以留到第二天。

$E_i \rarr E_{i + m}, (\infin, f)$ 送到快洗部。

$E_i \rarr E_{i + n}, (\infin, s)$ 送到慢洗部。

跑最小费用最大流即可。

P4553 80人环游世界

$N$ 个国家，按从东向西的顺序给出，某些国家之间有航线， $M$ 个人旅游，每个人可从任意国家开始，在任意国家结束，从东向西游历若干个国家，注意路线上相邻的两个国家必须由航线直接相连。

同时第 $i$ 个国家有且仅有 $V_i$ 个人游历。

问最少机票钱。

考虑先建出模型中的原图，在根据模型建出跑网络流的图。

可以从任意地方出发，所以设一个出发点 $ss$ ，出度 $M$ ，结束点 $tt$ ，入度 $M$ ，然后每个国家 $i$ ，出度 $V_i$ ，入度 $V_i$ 。

$ss \rarr i, 0; i \rarr tt, 0$ 可以从任意地方开始或结束。

若 $i$ 和 $j$ 之间有航线，机票一人 $w$ ，且 $i \le j$ ： $i \rarr j, w$ 自东向西，要航线相连。

根据模型，建出跑网络流的图，然后跑最小费用最大流即可。