2023年7月30日发(作者：)

网络流专题研究

福州一中 肖汉骏

预备知识(参见Amber论文)

网络和流

残留网络和增广路径

最大流和最小割

主要算法

最大流

增广路方法 Ford-Fulkerson method

一般增广路算法 Labeling algorithm

连续增广路算法

由陈启峰提出，竞赛中相当实用，近于O(m)

容量缩放增广路算法 Capacity scaling algorithm

最短增广路算法 Edmonds-Karp algorithm

连续最短增广路算法 Successive shortest augmenting path algorithm (Dinic

augorithm)

预流推进方法Preflow-push method

一般预流推进算法 Generic preflow-push algorithm

先进先出预流推进算法 FIFO preflow-push algorithm

最高标号预流推进算法 Highest-label preflow-push algorithm (Relabel-to-Front

algorithm)

最小费用流

最小费用路方法

一般最小费用路算法(SPFA找增广路，复杂度近于O(mf)，竞赛中实用)

注意：初始流的费用必须保证是在所有同流量流中最小的。 原始-对偶算法

消圈方法

一般消圈算法

网络单纯形法

常见变形

多源多汇问题

可通过增添超级源和超级汇解决。

点有容量或费用

可以尝试拆一个点为一入点一出点，将点的限制转移到入点到出点的边上。

重边、无向边和自环的处理

对于使用边链表存储的图，重边一般不需要特殊处理。但当重边的数量太多以至于显著影响算法效率时，可以考虑将相同起点终点的边的容量相加。

而无向边则可以看做是在两个方向上都只要求Flow小于Capa即可。

而最小费用流问题中的重边却反而成为一种处理复杂权函数的手段。根据题目要求或者问题性质，可以为重边列出一个费用随流量变化的函数。如果将这个函数的离散点顺次相连，得到的是若干斜率不断增大的折线段，则可为每段折线段建立一条边，根据最小费用流的性质，重边选择的必然是连续的一段。

给定流值的情况

可以增设一个源，向原来的源连一条容量为给定流值的边。

或者在每次增广的时候，直接将源的可改进量设为到给定流值的差。

或在回溯增广的时候，将路径的增广量同到给定流值的差比较后取小。

有上下界的流问题

注意到下界必须被满足，可以将所有必要弧抽取，经过新建的源和汇。但这时必须为原来的汇到源增添一条容量为无穷大的边，使之成为满足流量平衡条件的普通节点(注意，汇到源的流量实际上就是原网络的流值)。再运行最大流算法得到一个可行流。

另一方面，可以先满足下界，此时有一些点不满足流量平衡条件。而这可以用多源多汇问题解决。

若求的是最大流，则可以在可行流的基础上进行增广。

如果求的是最小可行流，则可以通过交换源汇，去除新增的点和边后运行最大流，将多余的流抵消。也可以通过二分汇到源的容量，运行可行流。

最大费用流

将费用取负，运行最小费用流算法。

或将SPFA的大于号反向。

可行最小费用流

从T向S连边，在这基础上找负权圈增广。 分离必要弧，使用最小费用流进行增广。

单位容量网络流

在构图上，可以利用只有两种取值的特殊性，容量用true和false表1和0，流量用true表1或-1，用false表0。则可以增广当且仅当xor的结果为true，增广可以直接变为相反的布尔常量。

而单位容量网络的另一个重要性质是增广次数不超过N次。则一般增广路算法的增广次数得以改进。

动态流

可以对时间拆点，建立层次图处理。

几个构图的思考方向

流表方案

【例1】 奶牛的新年晚会《算法艺术与信息学竞赛》p315

注意到奶牛和食物具备“会做”这样的关系，且其选择也只有做1盘与不做两种。而对每头奶牛有盘数限制k，对每种食物也有相应的上限值。则二分图模型呼之欲出。

【例2】 圆桌吃饭问题《算法艺术与信息学竞赛》p319

注意到幼儿园和桌子有“派出小朋友入座”这样的关系，且其选择也只有派1个与不派两种。而对幼儿园的人数和桌子的人数都有上限值。则也可很容易想到二分图模型。

【例3】 赛车问题 [2002][金恺]网络流应用

注意到两人的赛车均有上场次数的限制。而每次比赛均是某两辆车的对决。则就可以建立二分图模型，利用网络流解决。

【例4】 混合图的欧拉回路《算法艺术与信息学竞赛》p324

注意到边和点具有“为点增加入度”的关系，可以首先统计出每个顶点需要的入度，然后为每个点和边给出容量限制。

另外一种方法是对混合图任意定向，然后统计需要反向的边的个数。反向边对于原起点来说增加了入度，对原终点来说了减少入度。如果某点的入度要增加，则可从源向它连边；如果入度需要减少，则可以向汇连边。最后只要检查所有从s出发或到达t的边是否全部满载。

注意到在这种二分图上的增广实际上在对应的原图中就是找一条路径，使得头尾顶点都被改进。这便是一种调整思想。

【例5】 取整矩阵 Yali Train Day12

注意到每个元素只有取下整和取上整两种选择，而每行每列对相应元素取上整的次数有上下界。则可以通过求有上下界的最大流解决。

而另一种思想是随机确定是取上整还是取下整，再根据要求进行调整。每次先试图找一个行列的优化方向一致的格子进行优化。再试图找一个不满足条件的格子，将数值移动到同行/同列的格子中。 【例6】 矩阵 CTSC2007

注意到b非0即1。而每行每列对相应元素取1的次数有上下界，则可以通过求有上下界的最大流解决。

而另一种思想是随机确定是取上整还是取下整，再根据要求进行调整。每次先试图找一个行列的优化方向一致的格子进行优化。再试图找一个不满足条件的格子，将数值移动到同行/同列的格子中。

这实际上就是利用了增广过程在原问题中的映射。

【例7】 列车调度 [2002][金恺]网络流应用

本题每辆列车只能进出站一次，而一旦选择某辆列车，下一辆可选列车也被确定。此时的一个单位流对应的应该是一个车道。而点有容量则可以利用拆点法。于是便要解决一个最小费用流问题。

【例8】 餐厅问题 [2002][金恺]网络流应用

本题每天都有对毛巾的需求，而毛巾的来源有多种，去向也有多种，则可以考虑对每天进行拆点。此时的一个单位流对应的是一条毛巾，由于每天的弧必须被满足，则是一个有上下界的可行费用流问题。

也可以重新构图，直接利用最小费用最大流解决。

还可以根据增广的特殊性，贪心解决。

常用技巧

注意处理对象以及对象间的关系。如例1和例2，都提供了3个对象，要仔细分析具体的限制在哪些对象上，什么对象将另两个串联起来。

注意分析对象身上的限制，可能有多种变形，比如单纯的上限，又或是上下界均有。但共同点是相连的边在两个对象的计算方式都是一样的。比如例1中对盘数的统计，例2中对人数的统计，是平权的。挖掘出平权的计数关系，容易分析出什么是点，什么是边。

割表方案(可参见Amber论文)

【例1】 最大密度子图

结合01分数规划的一般做法，对答案进行猜测，转而求解一个最大化问题。

【例2】 最大获利 NOI2006

首先可以将边变为点，利用割所具有的性质，将边点依赖关系用容量为正无穷的边表示。然后利用最小割这个优化工具，从问题反面考虑，计算最小代价。

更优的办法是Amber提出的。注意到边权非负，则可以贪心地选择点导出子图。而点导出子图的权和不方便计算，可从反面考虑，用S集中的总边权和减去割表示。为了利用最小割这个优化工具，将每个点连到汇的代价设为选入S集中的代价，为建设费用，连到源的代价设为选入T集中的代价，为总边权和。而原图的边容量可直接设为边权。

【例3】 最优压缩 Yali Train Day4

注意到每个元素只有V0和V1两种选择，而权的计算实际上对应于点的变化以及边的变化。也就是只有V0与V1之间的边才计入代价。则容易想到割，并用与源和汇有关的边容量处理点权。

常用技巧

1.

2.

3.

4.

不连通。任意一条s-u-v-t路径都会被割截断。

两类点。将xor操作变为割。

用正无穷容量排除不参与决策的边。

利用与源和汇有关的边容量处理点权。连到汇的容量设为选入S集中的代价，连到源的容量设为选入T集中的代价。

5. 反向思考，充分利用最小割这个优化工具。

其他

1. 对时间的处理。可以考虑拆点，建立分层图解决。

2. 矩阵类型的题目常常用二分图进行构图。这是由行列以及元素的天然关系决定的，限制在行列上，由元素将其联系在一起。有时也使用奇偶染色构图，此时相邻关系是考察重点。有的还要进行离散化，例如有障碍棋盘上互不攻击的车的个数，就是先对连续空白段进行离散化而得的。

利用特殊性进行增广

【例1】 二分图匹配问题

由于二分图匹配问题均是单位流量，且连边方式十分特殊，可以只存储Y部节点的匹配情况，利用CQF式的网络流进行优化。速度非常可观。

【例2】 剪刀石头布 WC2007

首先进行问题转化：注意到剪刀石头布情况实际上对应一个长度为3的环。而非剪刀石头布情况这对应一个拓扑的环，其中有一个顶点有两条出边，另一个顶点有两条入边。则要求剪刀石头布情况尽量多，就是要求顶点的入边平方和尽量小。

于是可以为尚未确定的边建立节点，如果边点存在邻接关系，则连接一条边。点的权可以用到汇的边上的费用来表示，实际上是一个凸函数。这就可以利用重边的手段处理了。

观察本网络的增广过程，相当于选取一条路径，将其反向，如果解更优的话则保留改动。这也就是调整法的一种实现了。

【例3】 数据备份 APIO2007

首先可以证明选择的必然是k条边数为1的线段，而要求权和最小。这显然是一个最小费用最大流问题。但本题数据规模极大，必须另找方法。

注意到每次进行增广的时候，或者是直接添加一条长度为1的线段。或是将连续交错的线段全部反向，则一旦形成连续交错线段，就不会改变。

这可以使用映射堆进行优化。每次删除一个权最小的线段，并将前后线段删除，把当前线段的权修改为前后线段的和减去当前线段的权即可。

其他

对于一些有向图的问题，由于增广路的特殊性，调整方法往往是对一条链反向。分析时可以紧抓入度或紧抓出度，结合一起分析反而增大难度。

对每个元素有两种选择的问题，可以尝试任意选择一种，再根据限制进行构图。