网络流 ProMax 学习笔记

· · 算法·理论

本文主要讲一些网络流相关的 trick。

1. 流相关问题的套路

数据结构优化建图

数据结构优化建图是比较简单的套路，在此就不赘述。

例题：

一天，Arietta 准备去探访 Velding。临行前她再次弹起了琴。所有的 n 个音符形成一棵由音符 C（1 号节点）构成的有根树，每个音符可以选择弹奏一次或不弹奏。每一个音符有一个音高 H_i。Arietta 有 m 个力度，第 i 个力度能弹出 D_i 节点的子树中，音高在 [L_i,R_i] 中的任意一个音符。为了乐曲的和谐，Arietta 最多会弹奏第 i 个力度 T_i 次。Arietta 想知道她最多能弹出多少个音符。保证 1 \le n, m \le 10000，1\le H_i,T_i,P_i\le N，1\le L_i\le R_i\le N。

这道题是比较明显的网络流。对于每一个力度，我们建一个点，然后源点往这个点连边。这个点再往 D_i 子树中音高在范围内的点连流量为 1 的边。最后树上每个点往汇点连容量为 1 的边。最后跑最大流，答案就是最大流。

但是，树上的点个数太多了。那么如何优化建图呢？注意到子树的 dfn 序连续，并且每个询问对应的音高是个区间。那么如果在平面坐标系上，把每个点的 dfn 序设为 x 坐标，每个点的音高设为 y 坐标，每个力度连向的点，对应平面上的一个矩形内的点。

得到了这个性质后，我们尝试来优化一下建图。回忆起来有个东西叫 KDT，2DT（2 维 KDT）的节点对应的范围是一个矩形。那么发现我们其实可以用 2DT 优化建图。具体的，我们对 2DT 上每个节点，向其儿子连容量为 1 的边。然后每个力度往力度对应的矩形在 2DT 上的节点连边。这样的话，边的个数就很少了。就可以跑最大流了。

动态建边

例题：

有一些学生需要分班，一个班最多 q 个人，每个班由一个老师负责。有 n 种学生，第 i 种学生有 p_i 个，每个学生要分到一个班中。有 m 个老师，第 i 种学生与第 j 个老师之间有参数 a_{i,j},b_{i,j},c_{i,j}，其中 a_{i,j},b_{i,j},c_{i,j} > 0。一个第 i 种学生在第 j 个老师的第 k 个班上，则会产生 a_{i,j}k^2+b_{i,j}k+c_{i,j} 的疲劳度。 易得结论：一个老师可以管很多个班，但显然疲劳度积累非常快，不如分给其他老师。问怎么分配学生，使得所有老师的疲劳度之和最小？

先考虑如下的建图方式。 源点 s 向每种学生节点 i 连边，容量 p_i，费用 0。 老师 \to 班级节点 (j, k)，代表第 j 个老师开的第 k 个班。 学生节点 i \to 节点 (j, k)，容量 q，费用 f(i, j, k)。 节点 (j, k) \to 汇点 t：容量 q，费用 0。

这个建图方式边数太多了。注意到 f(i, j, k) 随 k 递增而递增。所以我们可以只为每个老师建立第 1 个班的节点 (j, 1)。在寻找增广路时，如果某条路径流经了节点 (j, k)，说明该班级已被使用。此时创建节点 (j, k+1) 及其相关边。这样的话可以有效地减少边数，减少空间和时间复杂度。

模拟费用流

模拟费用流，顾名思义，就是用数据结构或贪心来模拟网络流的建图和寻找增广路的过程。当网络流的图具有极其特殊的性质（如树结构、序列结构、明显的单调性等），我们就可以考虑利用这些性质，用优先队列、线段树或平衡树来手动维护增广路和退流（反悔贪心）的过程。

例题 ：

环上有 n（1\le n \le 5*10^4）个位置，位置 i 初始时有 a_i 个球。每次操作你可以把一个球移到它左边或右边相邻的位置上。试求最小的操作次数，使得最终对每个 i，第 i 个位置球的个数在 l_i 和 r_i 之间。其中满足 \sum\limits_{i=1}^nl_i\le \sum\limits_{i=1}^na_i \le \sum\limits_{i=1}^nr_i。

这题如果不考虑时限的话是一个非常简单的的上下界网络流，但放在 5 \times 10^4 的环上，肯定会 TLE。我们考虑模拟费用流或者。设 x_i 表示第 i 个位置向第 i+1 个位置传递了多少个球（为负则表示反向传递）。根据题意，我们有流量平衡条件 l_i \le a_i + x_{i-1} - x_i \le r_i。

我们需要最小化 \sum |x_i|。由于这是一个环，我们可以将所有 x_i 用 x_1 表达出来，即 x_i = x_1 + C_i，其中 C_i 是一段区间。问题转化为求一个 x_1，使得 \sum |x_1 + C_i| 最小，用线段树或者 Slope Trick 维护折线，我们可以模拟这个流的代价，从而在 O(n \log n) 内解决。

例题 2：

你有一张世界地图，并且知道各国家之间所有可用的交通路线。每条路线连接两个国家，并且有一个固定的费用，每一个军队沿该路线移动都需要一个单位的费用。这些路线把国家连成一棵树。你知道目前你的所有军队所在的位置，以及在每个国家至少需要放置多少军队来征服它。你至少需要花多少钱移动你的军队来征服世界？

这是经典的树上模拟费用流。建图非常显然，源点向军队连边，国家向汇点连边，树上相邻节点互相连边。寻找最小费用等价于在树上贪心地进行匹配。 我们可以在树上自底向上合并。对于每个节点，我们维护两个可并堆,一个维护该子树内尚未匹配的军队（提供流），另一个维护该子树内需要被征服的国家的空位（需求流）。每次在 LCA 处取出代价最小的军队和空位进行匹配，并把代表反悔操作的元素（即反向边）重新插回堆中。

例题 3：

游戏由 n 个城市构成，用 1 到 n 的整数编号。每次到达一个城市必须且只能完成一个任务。通道总共有 m 条，通道 (u,v) 只允许至多通过 w(u,v) 次。奇怪的是，若 u_1<u_2，则 v_1 \le v_2。求完成所有的任务最少需要使用多少次转送卷轴。

转送卷轴的次数本质上就是求图允许点相交的最小路径覆盖，或者说是带有下界的网络流。但这道题给出了一个单调性质,若 u_1<u_2，则 v_1 \le v_2。这说明通道的连线在某种意义上是不交叉的，

有了这种性质，连边就不会出现复杂的交错，我们在跑网络流的时候，实际上可以直接用贪心来模拟：按编号顺序，利用数据结构维护当前可用的最优前驱节点，直接贪心连边。这就把原本 O(V^2E) 的网络流优化到了 O(N \log N) 的数据结构模拟。

2. 最小割

最小割是网络流中最灵活、最能玩出花样的部分。根据最大流最小割定理，最小割往往用于处理二元选择、代价最小化、冲突解决等问题。

最小割的常见套路

最小割最经典的套路就是割掉一条边代表付出一种代价或做出一种选择，并且要保证 S 和 T 不连通。常见的模型包括最大权闭合子图、二元关系模型等。

例题 1：

给 n 个点 m 条边的无向图 G=(V,E)，需要选出一个点的非空子集 V'\subseteq V\wedge V'\ne \varnothing，取出这些点对应的边 E'。要使得边数除以点数 \frac{|E'|}{|V'|} 最大。

遇到分数规划 \max \frac{A}{B}，先二分答案 g。条件转化为判断是否存在子集使得 |E'| - g|V'| > 0。

把原图的点看作闭合子图中的点。我们可以转化，每个点一旦被选，它就贡献了它的度数。具体建图为，源点 S 向每个点连容量为 m 的边，每个点向汇点 T 连容量为 m + 2g - deg(v) 的边。原图中的无向边 (u,v) 拆成两条有向边互相连，容量为 1。求最小割后，判断 \frac{(n \times m - \text{min\_cut})}{2} 是否大于 0 即可更新二分边界。

例题 2：

切糕的形状是长方体。我们将切糕视作长 P、宽 Q、高 R 的长方体点阵 (x,y,z)，每个点有一个非负的不和谐值 v(x,y,z)。切面需与每个纵轴有且仅有一个交点 f(x,y)。相邻纵轴上的切割点不能相距太远：若 |x-x'|+|y-y'|=1，则 |f(x,y)-f(x',y')|\le D。求总的不和谐值 \sum_{x,y}v(x,y,f(x,y)) 最小的切割方案。

如果不考虑光滑性，我们直接对每个纵轴建一条链，S \to (x,y,1)，(x,y,z) \to (x,y,z+1)，(x,y,R) \to T，边的容量为对应的 v(x,y,z)。割掉哪条边就代表 f(x,y) 取哪个高度。 现在有了 |f(x,y)-f(x',y')|\le D 的限制。也就是说，如果旁边柱子割得太低，当前柱子就不能割得太高。我们只需要对于相邻的坐标，从当前纵轴的点 (x,y,z) 向相邻纵轴的点 (x',y',z-D) 连一条容量为 \infty 的有向边。这样如果高度差超过 D，无穷大的边就会导通，导致 S 和 T 依然连通，从而强迫最小割寻找符合规范的切法。

例题 3：

对于某一条无向图 (V,E) 中的边 e，至少需要多少代价可以保证 e 边在这个无向图的最小生成树中。一次单独的操作是指：先选择一条图中的边 e'，再把图中除了这条边以外的边，每一条的权值都减少 1。

选择一条边，其他边权值减 1，等价于只让选定边的权值加 1，其他边不变，因为我们只关心相对大小。

要让 e=(u,v) 必定在最小生成树中，根据 Kruskal 算法，在将边 e 加入时，u 和 v 必须不能连通。也就是说，图中所有权值 \le w(e) 的边，不能把 u 和 v 连通。因此，我们要做的就是删掉（权值加 1，代价为 1）一些权值 \le w(e) 的边，使得 u 和 v 不连通。 这显然是一个最小割问题，我们把原图中所有权值 \le w(e) 的边拿出来建图，容量全部设为 1，以 u 为源点，v 为汇点跑最小割，最大流即为最小代价。

例题 4：

有 n（\le 100）个人进行单循环赛，共需要进行 C_n^2 场，每一场一定一方赢另一方输。现在已知其中一部分场次的结果，你需要指定剩余场次的结果，使得出现“剪刀石头布”的三元组尽量多。

设第 i 个人已经确定赢了 w_i 轮，最终赢了 v_i 轮。剪刀石头布的三元组其实就是三元环。任意取三个人，总三元组数量是 \binom{n}{3}。当且仅当其中一个人赢了另外两个人，这三个人构不成三元环。

因此，非三元环的数量等于 \sum_{i=1}^n \binom{v_i}{2}。我们要最大化三元环，就是要最小化 \sum \binom{v_i}{2}。

这是一个费用随流量增加而呈二次函数递增的模型。由于 \binom{x+1}{2} - \binom{x}{2} = x，我们可以用最小费用最大流解决：对于每场未确定的比赛建一个节点，源点向比赛连容量 1 费用 0 的边；比赛向对应的两个人连容量 1 费用 0 的边；每个人向汇点连若干条容量为 1、费用依次为 w_{i}, w_{i}+1, w_{i}+2 \dots 的边。跑最小费用最大流即可。

保序回归

下面介绍一种一维的简单的保序回归问题的做法。给定序列/变量，赋予每个变量一个值，最小化 \sum w_i |x_i - c_i|^p。 当 p=1时，我们可以使用整体二分 + 最小割来解决。

二分当前的值域区间 [L, R]，设 mid = \lfloor \frac{L+R}{2} \rfloor。对于参与当前层二分的所有点建图，若当前点取值 \le mid，则划分到 S 集；若取值 > mid，则划分到 T 集。根据偏序限制 x_u \le x_v（即如果 v \le mid，那么 u 必须 \le mid），我们连一条从 v 到 u 容量为 \infty 的边。求最小割后，属于 S 的点继续去 [L, mid] 递归，属于 T 的去 [mid+1, R] 递归。

例题：

数轴上有 n 栋房子已经建立，第 i 栋房子的坐标为 x_i。还需要建立 m 栋房子，其中房子的坐标可以相同。给 (n+m)\times(n+m) 的自然数系数表 a，a_{i,j}=a_{j,i} 表示第 i 栋房子和第 j 栋房子住户的亲密度。住户 i 和 j 的见面疲劳度为 a_{i,j}|x_i-x_j|，问 m 栋房子最佳选址以后，最少的所有住户总疲劳度。

绝对值的最小化都可以转化为二元决策的叠加。我们可以整体二分坐标 x，每次二分判定一个房子是建在当前 mid 的左侧还是右侧。 a_{i,j}，房子 i 和 j 之间连一条容量为 a_{i,j} 的无向边。这样通过整体二分配合最小割，最终的坐标就是最优解。

最小割树

对于一张无向图，全图任意两点之间的最小割其实只有至多 n-1 种不同的值。最小割树可以在 n-1 次最小割运算内，把原图的割压缩成一棵树。树上两点间的最小边权，就是原图中这两点间的最小割。

例题：

给定一张 n 个点 m 条边的无向连通图，Q 次询问，每次询问两点之间的最小割。两点间的最小割是这样定义的：原图的每条边有一个割断它的代价，你需要用最小的代价使得这两个点不连通。

这是最小割树的模板题。由于 Q 很大，不可能每次询问跑一次网络流。我们通过分治，一开始所有点在一个集合里，每次任选两个点作为 S 和 T 跑最小割，把集合按照 S 连通块和 T 连通块分成两半，并在最小割树中连一条边，边权为本次的最小割。递归执行直到每个集合只有一个点。最后 Q 次询问就是在最小割树上求路径上的最小值。

最小割与强连通性

很多时候我们不仅需要求出最小割的值，还需要求出哪些边可能在最小割中，哪些边一定在最小割中。 这就需要利用跑完 Dinic 后的残量网络。在残量网络上跑 Tarjan 算法求出所有的强连通分量。

结论如下：

  1. 边 (u,v) 可能在最小割中：边在原图中满流，且 u 和 v 在残量网络中属于不同的 SCC。
  2. 边 (u,v) 一定在最小割中：边在原图中满流，且 u 所在 SCC 与源点 S 同属一个 SCC，v 所在 SCC 与汇点 T 同属一个 SCC。

例题 1：

给出 n 个节点 m 条边的有向图，再给出其中的两个点 s 和 t。对于每条边，输出是否存在一种最小割包含这条边，是否任何一种最小割都包含这条边。

这是上述结论的模板题。正向建图跑完最小割之后，拿着残量网络跑一遍 Tarjan 求强连通分量。然后再枚举原图每一条边，根据上述那两条结论进行判断即可。

例题 2：

有 n（\le10000）座城市，其中 m 对城市之间不是贸易伙伴，其他都是贸易伙伴，伙伴是双向的。如果一些城市两两之间都是贸易伙伴，则这些城市构成城市群。最开始所有的城市可以被划分成不超过两个城市群。现在需要选出一对不是贸易伙伴的城市，给它们建立贸易伙伴关系后，能使得最大的城市群至少增加 1 座城市。问这 m 对不是贸易伙伴的城市对哪些满足条件。

城市群是完全图，不超过两个说明原图可以被两个完全图覆盖。也就是说原图的补图是一个二分图。 求最大城市群，就是求原图的最大团，也就是求补图的最大独立集。对于二分图，最大独立集 = 点数 - 最大匹配。 题目转化为：在补图（二分图）中，删去哪一条边，可以使得二分图的最大匹配减小 1。这就转化为求二分图匹配中，哪些边是最大匹配的必经边或者可行边。跑最大流，求完二分图最大匹配后，用强连通分量（通过残量网络求 SCC）判断即可找出所有满足条件的边。

3. 平面图

平面图具有一个非常有趣的性质：平面图的最小割等于其对偶图的最短路。 对偶图就是把平面图的面看作节点，把分割两个面的边看作连接面与面之间的边。

例题：

平面上的矿区划分成了若干个开发区域。平面图划分为了若干平面块。 有 m 个开采计划。每个开采计划都指定了一个由若干开发区域组成的多边形，一个开采计划的优先度被规定为矿量的总和÷开发区域的面积和。其中面积为 s 的开发区域的矿量为 s^2。依次对每个开采计划求出优先度，强制在线的。

这道题是一道经典的平面图转对偶图的应用。 我们要想求多边形内部包含的区域总面积和面积平方和，首先要把图里面所有的面建出来。采用极角排序的方法：

  1. 把每条无向边拆成两条互为反向的有向边。
  2. 对于每个点，将其所有的出边按照极角大小顺时针排序。
  3. 如果我们沿着有向边 u \to v 走，到了 v 之后，我们选择在极角序上位于反向边 v \to u 的顺时针下一条出边继续走。这样一直走，最终一定会回到起点，圈出来的就是一个多边形的面。

利用叉积计算这些面的面积。建出面之后，我们可以把整个图映射成一棵生成树，相邻的面有边相连。树根设为外层的面（代码中求出来的面积为负数）。处理树上面积和面积平方的前缀和。找到询问对应的每一条边。如果不是树边则不管。如果是树边，且儿子在询问范围内，则答案加上子树和，否则的话这条边的父亲在询问范围内，则答案减去子树和。