O(nm)的最大流，论文A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PR

2023-01-20 21:34 作者:昵称不能为空voidf 0人读过 | 我要投稿

原文链接：https://www.cs.princeton.edu/courses/archive/fall07/cos521/handouts/0.pdf

1988年的老文了，复杂度已经被去年3月份的https://arxiv.org/abs/2203.00671打爆，但是难得找到了实现代码，这里研究之余处于兴趣简单感性烤一下肉，出于水平问题可能会有错漏，有不理解的地方还请参见原文，毕设需要准备论文翻译的同学你看着办改~

参考代码：https://github.com/touqir14/MaxFlow/blob/main/src/lib/algorithms/sequential/ahuja_orlin.h

这篇文章的思想和预流推进很像，建议先看懂预流推进那一套再来。与其不同的是，算法流程和流的值有关，不能很好支持浮点数流的情况，是一个为整数最大流而优化魔改的预流推进。但是它和dinic一样，能够提供正确的残量网络，从而得到最小割的选边方案。

不需要前置知识和证明的请移步第三节。

注本文把arc译作边而不是弧，请默认每条边(i,j)都是指有向边i->j

0. ABSTRACT

这是一个 $O(nm%2Bn%5E2%5Clog%20U)$ 的整数最大流算法，U为最大边容量值，可以并行运算，优化为 $O(((nm%2Fk)%2Bn%5E2%5Clog%20U)%5Clog%20k)$ ，k为处理器数量。

1. NOTATION

首先上假设，咱们的网络没有重边自环、源点s不等于汇点t、没有无穷容量的边。

定义图 $G%3D(N%2CA)$ 为有向网络，每条边 $(i%2Cj)%5Cin%7BA%7D$ 拥有正容量 $u_%7Bij%7D$

一条有效的流是满足以下性质的函数 $x%3AA%5Cto%7BR%7D$ ：

对于所有的 $i%5Cin%7BN-%5C%7Bs%2Ct%5C%7D%7D$ ，有 $r_%7Bij%7D%3Du_%7Bij%7D-x_%7Bij%7D%2Bx_%7Bji%7D$ （性质1，说人话就是除了源汇点，每个点的入流量等于出流量，即流量平衡）
定义 $%5Csum%5Climits_%7B%5C%7Bj%3A(j%2Ct)%5Cin%7BA%7D%5C%7D%7Dx_%7Bjt%7D%3Dv$ ，且有 $v%5Cge0$ (性质2，定义汇点的入流量为价值v)
对于所有的边 $(i%2Cj)%5Cin%7BA%7D$ ，有 $0%5Cle%7Bx_%7Bij%7D%7D%5Cle%7Bu_%7Bij%7D%7D$ (性质3，即每条边的流量不能超过容量)

最大流问题就是找到这么个流函数x可以使得v最大化。

一条有效的预流也是一个函数，满足性质2和3，但对于所有的 $i%5Cin%7BN-%5C%7Bs%2Ct%5C%7D%7D$ ，有 $%5Csum%5Climits_%7B%5C%7Bj%3A(j%2Ci)%5Cin%7BA%7D%5C%7D%7Dx_%7Bji%7D-%5Csum%5Climits_%7B%5C%7Bj%3A(i%2Cj)%5Cin%7BA%7D%5C%7D%7Dx_%7Bij%7D%5Cge0$ (性质4，即入流量大于等于出流量，多出来那部分即后文要提到的超额流excess)

本文所述的算法在每个中间态维护一个预流。

对于给定的预流x，我们定义节点超额流(excess)为 $e_i%3D%5Csum%5Climits_%7B%5C%7Bj%3A(j%2Ci)%5Cin%7BA%7D%5C%7D%7Dx_%7Bji%7D-%5Csum%5Climits_%7B%5C%7Bj%3A(i%2Cj)%5Cin%7BA%7D%5C%7D%7Dx_%7Bij%7D$ 。

一个有正超额流的节点被叫做活点(active node)，我们定义源汇点的超额流为0，因此他俩都不是活点。对于给定的预流x，我们定义边上的残余容量(residual capacity，后文简称残量)为 $r_%7Bij%7D%3Du_%7Bij%7D-x_%7Bij%7D%2Bx_%7Bji%7D$ ,边(i,j)的残余容量表示在使用边(i,j)及其反边(j,i)的情况下，最大还能从i点向j点运送多少流量，而包含所有正残余容量的边的网络，则叫做残量网络（注：这个残量网络可以用于算s-t最小割，输出最小割的选边方案），下图画出了这几个定义：

我们定义关于点 $i%5Cin%7BN%7D$ 的邻接表A(i)为i的出边集，即 $A(i)%3A%3D%5C%7B(i%2Ck)%5Cin%7BA%3Ak%5Cin%7BN%7D%7D%5C%7D$ ，注意这里是不可重集合，而不是简单的列表（虽然在代码实现中洗过重边了这里还是用vector实现）。

距离函数 $d%3AN%5Cto%7BZ%5E%2B%7D$ 是一个从节点集到非负整数的映射。当距离函数d满足以下两个条件时，我们定义其为有效的：

C1. $e_i%3E%5CDelta%20%2F2%5C%20%5Ctext%7Band%7D%5C%20e_j%5Cle%20%5CDelta%2F2$
C2. 对于所有残量大于0的边(i,j)，有 $d(i)%5Cle%7Bd(j)%2B1%7D$

我们将上述两个条件合在一起称为有效性条件。

本文的算法在每次迭代中维护一个有效的距离函数。我们也把d(i)叫做节点i的距离标号(distance label)，由归纳法易证d(i)即为i到t在残量网络上的最短路。

本文只会推流满足d(i)=d(j)+1的边(i,j)（后文称为可行边）。本文所有算法除特别声明，默认基底(base)为2。

2. PREFLOW-PUSH ALGORITHMS

喜闻乐见的预流推进算法，历史咱们不译。

每一步的预流推进算法只使用本地信息（每个点上及其邻边和邻点存的信息）。除初始化和算完return外，每一次迭代中网络至少要包含一个活点，即一个非源汇且有正超额流的节点。每一步迭代的目标是选中一些活点并且把它的超额流送得离汇点更近（以有关距离标号的方式评估），如果这个点的超额流不能往更小距离标号的点推掉，那这个点的距离标号就要被提高。算法将在没有活点的时候终止。预流推进有以下几个操作：

预处理：把源点s的所有出边推满，把d(s)提到n，d(t)赋0，其他的点的标号贴个1（或者任何其他标号法也可以采用，比如从t反向bfs，根据步数贴标号）

推流(i)：选中比i点低1的邻点j，向j推 $%5Cmin(e_i%2Cr_%7Bij%7D)$ 单位的流，当这个推过去的流等于边残量rij时，我们定义这是一个饱和推流，否则叫做不饱和推流

重标号(i)：把i点的标号提到残量网络上被它的出边连至，且高度最低的点的高度+1，即 $%5Cmin%5C%7Bd(j)%2B1%3A(i%2Cj)%5Cin%7BA(i)%7D%5C%20%5Ctext%7Band%7D%5C%20r_%7Bij%7D%3E0%5C%7D$ 。重标号的目的是创造至少一个d(i)=d(j)+1的条件，以便流能被继续推走。

下图展示了图标1a中推流和重贴标号的过程，边上的数字表示这条边的残量。

预处理步骤完成了几个重要任务。它一次性把s点的流向周围推完，然后把s点标号贴为n，使其不可达。由于距离标号是非递减的（见引理1），我们能够在随后的步骤中保证残量网络不会再包含一条从s到t的有向路，所以也没有从s推更多的流的必要。

在本文提出的改进版预流推进算法中，需要一部分来自Goldberg与Tarjan(1986)给出的结论。我们引入了他们部分证明，以使得我们的结果更加逻辑自洽，感兴趣的读者可以自己去翻他俩讨论其它版本预流推进的原论文。

引理1：通用的预流推进算法会在每一步维护有效的距离标号。而且在每一次重标号操作中，受影响的节点的距离标号会严格递增。

证明：注意到预处理步骤创建了有效的距离标号，我们用归纳法假设距离函数在每次操作之前总是有效的（即满足前文的C1和C2条件）。一次在边(i,j)上的推流可能会新建一条残量大于0反边(j,i)，且导致一个新的条件 $d(j)%5Cle%7Bd(i)%2B1%7D$ 也必须被满足。此条件由推流操作自带的属性d(i)=d(j)+1得出，所以成立。使用边(i,j)的推流操作可能会导致此边残量用完而从残量网络上被删除，但这并不会影响距离函数的有效性。在重标号操作中，节点i的新标号 $d'(i)%3D%5Cmin%5C%7Bd(j)%2B1%3A(i%2Cj)%5Cin%7BA(i)%5C%20%5Ctext%7Band%7D%5C%20r_%7Bij%7D%3E0%7D%5C%7D$ 也总是满足有效性条件。重标号操作将执行于没有任何一条边(i,j)残量大于0且d(i)=d(j)+1时。由此得出， $d(i)%3C%5Cmin%5C%7Bd(j)%2B1%3A(i%2Cj)%5Cin%7BA(i)%7D%5C%20%5Ctext%7Band%7D%5C%20r_%7Bij%7D%3E0%5C%7D%20%3D%20d'(i)$ ，命题得证，并由此引出引理2：

引理2：在预流推进的每个中间状态中，对于每个有正超额流的节点i，在残量网络上总是有一条从i到s的有向路径。

证明：由Ford和Fulkerson提出的流结构理论，任何预流x可以在原网络G上被分解为一系列流的总和，沿着以下这些路径：

s到t的路径
s到活点的路径
有向环

令i为一个活点，对应于原图G的预流x。由流的分解，必然存在一条从s到i的路径，这是因为从s到t的路径以及有向环不会贡献节点i的超额流。此时反图P在残量网络上（这里应该是引了FF论文的定义或者结论），因此残量网络上存在一条从i到s的路径。

推论1：对于每个节点 $i%20%5Cin%20N%2C%20d(i)%3C2n$ 。

证明：最后一次节点i被重标号时，它有正超额流，因此，残量网络中包含一条长度至少为n-1的从i到s的路。由d(s)=n与条件C2可以推出 $d(i)%5Cle%20d(s)%2Bn-1%3C2n$ 。

引理2还意味着重标号步骤永远不会在空集上产生任何影响。

推论2：重标号次数总是少于 $2n%5E2$ 。

证明：每次重标号会至少将一个节点的标号提高1，另外由推论1可得，不存在可以被重贴超过2n次标号的节点。

推论3：饱和推流次数不会超过nm。

证明：设边(i,j)在某步之后残量用尽达到饱和（此时有d(i)=d(j)+1）。那么边(i,j)不可能输送更多的流，除非有流走反边从j送回给i（退流，此时有 $d'(j)%3Dd'(i)%2B1%5Cge%20d(i)%2B1%3Dd(j)%2B2$ ）。而退流至少得在d(j)被拔高了至少2才可能发生。因此由推论1，边(i,j)最多饱和n次，所以所有的边加在一起也不会超过nm次。（注意我们假设边(i,j)和(j,i)都在边集A里，所以残量网络中的边数不会超过m）

引理3：非饱和推流至多 $2n%5E2m$ 次。

证明：参见Goldberg and Tarjan (1986)。

引理4：算法随找到最大流而终止。

证明：当算法终止时，每个除源汇点外的节点的超额流都是0，所以最终的预流就是一个可行流。由于距离标号一直满足条件C1和C2且有d(s)=n，因此算法终止时，残量网络上不会含有从s到t的有向路径。此条件即为经典的Ford and Fulkerson的最大流算法的终止条件。

许多基于预流的算法，如Karzanov、Tarjan、Goldberg and Tarjan (1986)，的性能瓶颈在于非饱和推流次数。至于为何非饱和推流占得份子比饱和推流更多，部分是因为饱和推流会删掉残量网络中的边，这种现象导致了饱和推流顶多需要O(nm)次，且与推流的先后顺序无关。而非饱和推流不会修改残量网络的结构，所以更难算出它的操作次数上界。Goldberg (1985) 给出在节点遵循先入先出序处理时，非饱和推流次数是 $O(n%5E3)$ 的。Goldberg and Tarjan (1986) 使用动态树来优化了这套算法。Cheriyan and Maheshwari (1988) 证明了在每次用最高标号的节点推流时，非饱和推流可以降至 $O(n%5E2%5Csqrt%7Bm%7D)$ 次，并且这个上界很紧。他们也证明了通用预流推进 $O(n%5E2m)$ 和先入先出预流推进 $O(n%5E3)$ 这俩复杂度也很紧。在下一节，我们将展示如何使用scaling（技巧名称，后文保留原词不译）来戏剧化地降低非饱和推流次数至 $O(n%5E2%5Clog%20U)$ 。

3. THE EXCESS SCALING ALGORITHM （正篇）

就是说咱们用了一个叫做excess scaling的技巧来把预流推进非饱和推流的次数从 $O(n%5E2m)$ 优化到了 $O(n%5E2%5Clog%7BU%7D)$ 。基本思路是把拥有足够大超额流的节点往足够小超额流点推流，并保持这些超额流不要变得太大，咱们把这种算法叫做excess scaling algorithm（超额增量算法？）

本算法进行 $K%3D%5Clceil%20%5Clog%20U%20%5Crceil%2B1$ 次scaling，在每次迭代中，我们定义主导超额流算子Δ为2的幂，是一个对所有节点i满足 $e_i%5Cle%20%5CDelta%20$ （跳前章的读者注意，此处ei指节点i的超额流excess值）的最小整数。此外，每次新的scaling会令Δ减半。在一次scaling中，我们确保每次非饱和推流（没有用完某条边残量的推流操作，叫非饱和推流）会推送至少Δ/2单位的流，以此来限制这个Δ不会增高。为了保证每次非饱和推流推的是至少Δ/2的流，我们只考虑超额流大于Δ/2的节点。在这些拥有较大超额流的节点中，我们选中一个拥有最小距离标号的节点。这种选择可以确保流会被推到一个拥有较小超额流的节点去。我们证明了顶多在 $8n%5E2$ 次非饱和推流之后，Δ会降为相当于被除了个至少2的因子，并且一个新的scaling得以开始。在最多K次scaling操作后，所有的节点超额流都会降至0，至此我们可以得到最大流。

为了选中一个距离标号最小，且拥有超过Δ/2超额流的节点，我们需要维护2n-1个链表 $%5Ctext%7BLIST%7D(r)%20%3D%20%5C%7Bi%5Cin%20N%3Ae_i%3E%5CDelta%2F2%5C%20%5Ctext%7Band%7D%5C%20d(i)%3Dr%5C%7D%3Br%3D1%2C...%2C2n-1$ 。它们得支持O(1)的插入和删除指定元素。我们用变量level来表示上述这些列表中，下标值最小的非空列表的那个下标。

我们需要一些技巧来快速选中可行边（即满足距离标号d(i)=d(j)+1的边，推流的前提）。对每个节点i我们有出边邻接表A(i)，这个边的顺序可以随意，但一旦算法开始就不得修改。对于每个节点i我们插入一条特殊的null边于A(i)的尾部。然后做一下当前弧优化——对每个点i维护一个当前弧下标，指向一个能被i推流的候选边。一开始所有的当前弧都指向这个节点的第一条出边，每当当前弧已经不再是一条可行边，则令这个当前弧指向其邻接表中下一条边。当某个节点的边表已经被处理完毕时，它的当前弧指向我们预先放好的null边，此时这个节点要被重标号，然后我们令这个点的当前弧重新指向它的第一条出边。

4. COMPLEXITY OF THE ALGORITHM

本节将证明此算法能在 $O(nm%2Bn%5E2%5Clog%20U)$ 的时间内算出正确的最大流。

引理5：此excess scaling algorithm满足以下两个条件：

C3. 每次从i到j的非饱和推流至少会传送Δ/2单位的流量
C4. 不会有超额流在推流后超过Δ

证明：对于每次在边(i,j)上的推流，我们有 $e_i%3E%5CDelta%20%2F2%5C%20%5Ctext%7Band%7D%5C%20e_j%5Cle%20%5CDelta%2F2$ ，这是因为点i是超额流大于Δ/2且距离标号最小的点（译注：大往小1推，如果存在j有大于Δ/2的流，由最小标号的枚举顺序，那么它应该会先于这个i被枚举到，所以这个最小标号的条件可以保证我们最先枚举到的(i,j)一定满足上述条件）。同时由推流条件，有 $d(j)%3Dd(i)-1%3Cd(i)$ 。因此，通过推送 $%5Cmin%5C%7Be_i%2C%20r_%7Bij%7D%2C%5CDelta%20-%20e_j%5C%7D%5Cge%5Cmin%5C%7B%5CDelta%20%2F2%2C%20r_%7Bij%7D%20%5C%7D$ 单位的流，我们可以确保本次推流要么至少可以传送Δ/2单位的流，要么用尽这条边的容量而成为饱和推流。此外，这次推送只会增加j点的超额流，我们设 $e'_j$ 为j点被推流之后的超额流，则有 $e'_j%3De_j%2B%5Cmin%5C%7Be_i%2Cr_%7Bij%7D%2C%5CDelta-e_j%5C%7D%5Cle%20e_j%2B%5CDelta-e_j%5Cle%5CDelta$ 。所有节点的超额流因此会保持小于等于Δ。

当然也有别的做法可以保证算法运行过程中C3和C4条件总是成立，但取最小距离标号的超额流超过Δ/2是一种简单而高效的做法。

在C3和C4条件成立的情况下，推流操作可以被视为一种restrained greedy approach（受限制的贪心方法）。C3保证了从i到j的推流足够大而有效，C4保证了每次迭代不会有超额流超过Δ。特别地，节点i会留一些余地防止j的超额流超过Δ，而不是贪心地一股脑把自己的超额流全往人家身上推。保持最大超额流更低可能在实践和理论中更有用。它的主要影响是鼓励超额流能够在网络中分布得更平均，而这种分布应该可以令中间节点往汇点更容易地推流。这可能很重要，出于如下考虑：我们设想若干个点往j点推流使得j点的超额流非常大，此时j点不太能够把它的流往离汇点更近的地方推，在这种情况下，j点不得不重标号，使得它的标号增高，并且大多超额流得返还回去。我们可以维护C4条件从而避免这种“打太极”现象。

引理6：如果每次推流都满足条件C3和C4，那么非饱和推流在每次scaling中最多有 $8n%5E2$ 次。

证明：考虑势函数 $F%3D%5Csum_%7Bi%5Cin%20N%7De_id(i)%2F%5CDelta$ 。F的初始值在一次scaling中上界是 $2n%5E2$ ，因为ei上界是Δ，而d(i)上界是2n。在算法处理节点i的时候，以下两个情况之一必发生：

情况1：找不到任何能推流的边，这种情况在i点的当前弧到达A(i)尾部时发生。观察到如果一条边(i,j)已经是不再是可行边，那么它在d(i)被提高之前一直都不会是可以推流的可行边，因为d(j)是非递减的。因此，当i点不再有对外的可行边时，重标号会给d(i)提高至少1个单位，我们令提高的高度为ε，则F至多增加ε。对于所有的点i，由于d(i)在整个算法流程中不会提高超过2n个单位，所以在一次scaling迭代中，节点重标号给F带来的增量不会超过 $2n%5E2$ 。（实际上把所有的scaling加一起，F的增量也不会超过 $2n%5E2$ ）

情况2：找到了一条可以推流的可行边，推流有饱和和不饱和两种情况。在这两种情况下F都会减少。边(i,j)的非饱和推流会传送至少Δ/2的流量，由于d(j)=d(i)-1，这个操作会使F减少至少1/2个单位。因为一次scaling中F的初值加上F的增量总和不会超过 $4n%5E2$ ，这种情况不会发生超过 $8n%5E2$ 次。

定理1：scaling算法进行 $O(n%5E2%5Clog%20U)$ 次非饱和推流。

证明：Δ的初值是 $2%5E%7B%5Clceil%5Clog%20U%5Crceil%7D%5Cle2U$ 。由引理6，Δ将在至多 $8n%5E2$ 次的非饱和推流之后减半，并开始新一次迭代。在 $1%2B%5Clceil%5Clog%20U%5Crceil$ 次scaling后，Δ<1，此时由于s、t之外的点超额流都是0，算法得以得到一个可行流，且由引理4知此可行流即为最大流。

定理2：excess scaling algorithm的复杂度是 $O(nm%2Bn%5E2%5Clog%20U)$ 。

证明：此算法的复杂度由main中while的执行次数决定。每次循环中，要么触发一次对i点的推流或者重标号操作，要么变量level会增加。每次推流或重标号有以下两种情况：

情况1：推流被触发，其中饱和推流O(nm)次，非饱和推流 $O(n%5E2%5Clog%20U)$ 次，这种情况发生 $O(nm%2Bn%5E2%5Clog%20U)$ 次。

情况2：i的标号被提高。由推论1，这种情况对每个节点O(n)次，加起来一共 $O(n%5E2)$ 次。

因此算法会调用推流/重标号 $O(nm%2Bn%5E2%5Clog%20U)$ 次。我们需要在O(1)时间内找到一条边进行推流。考虑更新当前弧，在|A(i)|次迭代枚举完i点的边之后，情况2会发生，此时i点的标号会增高。因此，总开销是 $%5Csum_%7Bi%5Cin%20N%7D2n%7CA(i)%7C%3DO(nm)$ 再加上推流/重标号操作的开销，显然他们之和是 $O(nm%2Bn%5E2%5Clog%20U)$ 。

（译注：虽然我觉得在文初无重边的假设下，|A(i)|应该是O(n)，而不是O(m)的）

接着我们考虑重标号操作的时间开销。计算点i的新距离标号需要遍历i的所有出边A(i)，从而总计需要 $%5Csum_%7Bi%5Cin%20N%7D2n%7CA(i)%7C%3DO(nm)$ 的时间来完成所有的重标号操作。由于链表LIST(r)使用链接栈以及队列实现（咱们代码中还是老实手写了个双向链表），因此增加和删除一个任意元素是O(1)的。所以说更新这些链表不是复杂度的瓶颈。

最后，我们需要算出level的增加次数上限。在每次scaling迭代中，level的上界是2n-1，下界是1。因此，每次scaling中level的增加次数是它降低次数+2n。此外，level降低只可能发生在一次推流发生后，并且只是降1,。因此把所有的scaling操作加起来，它的增加次数是推流次数+ $2n(1%2B%5Clceil%5Clog%20U%5Crceil)$ ，所以总的还是 $O(nm%2Bn%5E2%5Clog%20U)$ 的。

5. REFINEMENTS

一些魔改可能可以提高本算法的实际运行效率而不会影响最坏情况下的复杂度，哥们说三种改法：

修改scale factor。
允许小部分非饱和推流。
尝试寻找不与汇点连通的点。（省流：global_relabel和gap优化）

第一是考虑scale factor怎么改，上边的算法用的是2，即每次循环完令Δ变为Δ/2。实际运行中，某些固定的整数scale factor $%5Cbeta%5Cge2$ 可以得到更好的结果。此时主导超额流算子Δ是最小的满足所有点的超额流不大于它的β的幂。且条件C3变更如下：

C3'. 每次i到j的非饱和推流传送至少Δ/β单位的流。

前面说的scaling算法可以小改以适配这个新的因子β，我们令 $%5Ctext%7BLIST%7D(r)%3D%5C%7Bi%5Cin%20N%3Ae_i%3E%5CDelta%2F%5Cbeta%5C%20%5Ctext%7Band%7D%5C%20d(i)%3Dr%5C%7D$ 。可以证明此时的魔改算法复杂度是 $O(nm%2B%5Cbeta%20n%5E2%5Clog_%7B%5Cbeta%7DU)$ 。以最坏情况去考虑，任何固定的β值都是最优的。实践中应该靠经验去调这个超参。

第二是考虑非饱和推流怎么推。我们前面说的算法是选中 $e_i%3E%5CDelta%2F2$ 的点进行非饱和或者饱和推流。其实我们也可以一直把这个点的流往外推，直到我们用完它的超额流或者推了一次至少Δ/2的非饱和流。这个修改可能会产生更多的来自i点的饱和推流甚至允许i点在流量低于Δ/2时仍进行推流。另一方面，前述的算法每次非饱和推流至少要推Δ/2，其实如果对于某个大于等于1的常量r，你能保证每r次非饱和推流能传送Δ/2单位的流量的话，你也能达成同样的复杂度。

第三是考虑实际运行中重标号导致的瓶颈。特别地，当d(i)超过n-2时，本算法可以得出此时在残量网络上已经不再有从i到t的路径。Goldberg (1987) 建议偶尔进行bfs扫描以让距离标号正确可能很有用（global_relabel操作），实际上这么做确实跑得飞快。

一个可选的办法是记 $n_k$ 为标号为k的点数，如果某次重标号中一个标号为k的点被拔高导致 $n_k$ 变0，则在残量网络上这些标号大于k的点不可能再与汇点连通。（一旦点j与汇点不再连通，它直到从j到t的基于长度的最短路是非递减时为止都会保持不连通。）我们避免选中这些点直到所有正超额流点都与汇点断开为止。此时多出来的超额流应该还给源点（不然得到的残量网络不对）。根据这个思想我们可以把算法设计成两个阶段，阶段1用预流（可以得到最大流的值），阶段2把预流转换成可行的最大流（可以得到残量网络，从而得到最小割的选边方案）。

（译注：如果只是需要最大流值，则没必要把阶段1之后其余点的超额流返还给源点，可以见networkx的preflow_push方法的value_only选项）

第六节的并行计算实现和第七节的相关研究这里视反馈可能打算新开一章来翻或者咕掉。

这里放点干货，以下上文提到的算法的代码实现均魔改自github.com/touqir14/MaxFlow/

洛谷最大流板题P4722：https://www.luogu.com.cn/record/99677685

洛谷最小割树板题P4897：https://www.luogu.com.cn/record/99812219

使用预流推进做的最小割树：https://www.luogu.com.cn/record/99006782

随机图上分别以hlpp、excess scaling、dinic作为最小割树的最大流提供算法的运行时间比较（dinic取自洛谷题解区，hlpp取自模板题运行时间最短的程序）：

文末提醒一下打竞赛的后辈，不要一味追求模板的运行效率，在赛场上应该优先选择码量少，打得快，修得快，跑得过的模板。ahuja_orlin的码量（至少在这份代码实现中）不小，带来的性能优化也比较有限。我的评价是它不适合在赛场上使用。如果你在找一份短小精悍的hlpp的话可以看看：https://github.com/kth-competitive-programming/kactl/blob/main/content/graph/PushRelabel.h

最后希望这篇论文翻译能够给在寻找有代码实现的网络流算法研究者一些帮助。

PS1：我试过给那份代码加当前弧优化，结论是跑得更慢了

PS2：我试过把那份代码的邻接表改为单维vector，结论是跑得更慢了

标签：

O(nm)的最大流，论文A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PR

O(nm)的最大流，论文A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PR的评论 (共条)

你可能也喜欢这些文章

最新发布的文章

O(nm)的最大流，论文A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PR

本文作者的其他文章

O(nm)的最大流，论文A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PR的评论 (共 条)

你可能也喜欢这些文章

最新发布的文章

O(nm)的最大流，论文A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PR的评论 (共条)