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

1988年的老文了，復(fù)雜度已經(jīng)被去年3月份的https://arxiv.org/abs/2203.00671打爆，但是難得找到了實(shí)現(xiàn)代碼，這里研究之余處于興趣簡(jiǎn)單感性烤一下肉，出于水平問(wèn)題可能會(huì)有錯(cuò)漏，有不理解的地方還請(qǐng)參見(jiàn)原文，畢設(shè)需要準(zhǔn)備論文翻譯的同學(xué)你看著辦改~

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

這篇文章的思想和預(yù)流推進(jìn)很像，建議先看懂預(yù)流推進(jìn)那一套再來(lái)。與其不同的是，算法流程和流的值有關(guān)，不能很好支持浮點(diǎn)數(shù)流的情況，是一個(gè)為整數(shù)最大流而優(yōu)化魔改的預(yù)流推進(jìn)。但是它和dinic一樣，能夠提供正確的殘量網(wǎng)絡(luò)，從而得到最小割的選邊方案。

不需要前置知識(shí)和證明的請(qǐng)移步第三節(jié)。

注本文把a(bǔ)rc譯作邊而不是弧，請(qǐng)默認(rèn)每條邊(i,j)都是指有向邊i->j

0. ABSTRACT

這是一個(gè)??的整數(shù)最大流算法，U為最大邊容量值，可以并行運(yùn)算，優(yōu)化為?，k為處理器數(shù)量。

1. NOTATION

首先上假設(shè)，咱們的網(wǎng)絡(luò)沒(méi)有重邊自環(huán)、源點(diǎn)s不等于匯點(diǎn)t、沒(méi)有無(wú)窮容量的邊。

定義圖??為有向網(wǎng)絡(luò)，每條邊??擁有正容量?

一條有效的流是滿(mǎn)足以下性質(zhì)的函數(shù)?：

1. 對(duì)于所有的?，有??（性質(zhì)1，說(shuō)人話(huà)就是除了源匯點(diǎn)，每個(gè)點(diǎn)的入流量等于出流量，即流量平衡）

2. 定義?，且有??(性質(zhì)2，定義匯點(diǎn)的入流量為價(jià)值v)

3. 對(duì)于所有的邊，有??(性質(zhì)3，即每條邊的流量不能超過(guò)容量)
   

最大流問(wèn)題就是找到這么個(gè)流函數(shù)x可以使得v最大化。

一條有效的預(yù)流也是一個(gè)函數(shù)，滿(mǎn)足性質(zhì)2和3，但對(duì)于所有的?，有(性質(zhì)4，即入流量大于等于出流量，多出來(lái)那部分即后文要提到的超額流excess)

本文所述的算法在每個(gè)中間態(tài)維護(hù)一個(gè)預(yù)流。

對(duì)于給定的預(yù)流x，我們定義節(jié)點(diǎn)超額流(excess)為?。

一個(gè)有正超額流的節(jié)點(diǎn)被叫做活點(diǎn)(active node)，我們定義源匯點(diǎn)的超額流為0，因此他倆都不是活點(diǎn)。對(duì)于給定的預(yù)流x，我們定義邊上的殘余容量(residual capacity，后文簡(jiǎn)稱(chēng)殘量)為,邊(i,j)的殘余容量表示在使用邊(i,j)及其反邊(j,i)的情況下，最大還能從i點(diǎn)向j點(diǎn)運(yùn)送多少流量，而包含所有正殘余容量的邊的網(wǎng)絡(luò)，則叫做殘量網(wǎng)絡(luò)（注：這個(gè)殘量網(wǎng)絡(luò)可以用于算s-t最小割，輸出最小割的選邊方案），下圖畫(huà)出了這幾個(gè)定義：

我們定義關(guān)于點(diǎn)的鄰接表A(i)為i的出邊集，即?，注意這里是不可重集合，而不是簡(jiǎn)單的列表（雖然在代碼實(shí)現(xiàn)中洗過(guò)重邊了這里還是用vector實(shí)現(xiàn)）。

距離函數(shù)??是一個(gè)從節(jié)點(diǎn)集到非負(fù)整數(shù)的映射。當(dāng)距離函數(shù)d滿(mǎn)足以下兩個(gè)條件時(shí)，我們定義其為有效的：

• C1.?

• C2. 對(duì)于所有殘量大于0的邊(i,j)，有
  

我們將上述兩個(gè)條件合在一起稱(chēng)為有效性條件。

本文的算法在每次迭代中維護(hù)一個(gè)有效的距離函數(shù)。我們也把d(i)叫做節(jié)點(diǎn)i的距離標(biāo)號(hào)(distance label)，由歸納法易證d(i)即為i到t在殘量網(wǎng)絡(luò)上的最短路。

本文只會(huì)推流滿(mǎn)足d(i)=d(j)+1的邊(i,j)（后文稱(chēng)為可行邊）。本文所有算法除特別聲明，默認(rèn)基底(base)為2。

2. PREFLOW-PUSH ALGORITHMS

喜聞樂(lè)見(jiàn)的預(yù)流推進(jìn)算法，歷史咱們不譯。

每一步的預(yù)流推進(jìn)算法只使用本地信息（每個(gè)點(diǎn)上及其鄰邊和鄰點(diǎn)存的信息）。除初始化和算完return外，每一次迭代中網(wǎng)絡(luò)至少要包含一個(gè)活點(diǎn)，即一個(gè)非源匯且有正超額流的節(jié)點(diǎn)。每一步迭代的目標(biāo)是選中一些活點(diǎn)并且把它的超額流送得離匯點(diǎn)更近（以有關(guān)距離標(biāo)號(hào)的方式評(píng)估），如果這個(gè)點(diǎn)的超額流不能往更小距離標(biāo)號(hào)的點(diǎn)推掉，那這個(gè)點(diǎn)的距離標(biāo)號(hào)就要被提高。算法將在沒(méi)有活點(diǎn)的時(shí)候終止。預(yù)流推進(jìn)有以下幾個(gè)操作：

預(yù)處理：把源點(diǎn)s的所有出邊推滿(mǎn)，把d(s)提到n，d(t)賦0，其他的點(diǎn)的標(biāo)號(hào)貼個(gè)1（或者任何其他標(biāo)號(hào)法也可以采用，比如從t反向bfs，根據(jù)步數(shù)貼標(biāo)號(hào)）

推流(i)：選中比i點(diǎn)低1的鄰點(diǎn)j，向j推??單位的流，當(dāng)這個(gè)推過(guò)去的流等于邊殘量rij時(shí)，我們定義這是一個(gè)飽和推流，否則叫做不飽和推流

重標(biāo)號(hào)(i)：把i點(diǎn)的標(biāo)號(hào)提到殘量網(wǎng)絡(luò)上被它的出邊連至，且高度最低的點(diǎn)的高度+1，即??。重標(biāo)號(hào)的目的是創(chuàng)造至少一個(gè)d(i)=d(j)+1的條件，以便流能被繼續(xù)推走。

下圖展示了圖標(biāo)1a中推流和重貼標(biāo)號(hào)的過(guò)程，邊上的數(shù)字表示這條邊的殘量。

預(yù)處理步驟完成了幾個(gè)重要任務(wù)。它一次性把s點(diǎn)的流向周?chē)仆辏缓蟀裺點(diǎn)標(biāo)號(hào)貼為n，使其不可達(dá)。由于距離標(biāo)號(hào)是非遞減的（見(jiàn)引理1），我們能夠在隨后的步驟中保證殘量網(wǎng)絡(luò)不會(huì)再包含一條從s到t的有向路，所以也沒(méi)有從s推更多的流的必要。

在本文提出的改進(jìn)版預(yù)流推進(jìn)算法中，需要一部分來(lái)自Goldberg與Tarjan(1986)給出的結(jié)論。我們引入了他們部分證明，以使得我們的結(jié)果更加邏輯自洽，感興趣的讀者可以自己去翻他倆討論其它版本預(yù)流推進(jìn)的原論文。

引理1：通用的預(yù)流推進(jìn)算法會(huì)在每一步維護(hù)有效的距離標(biāo)號(hào)。而且在每一次重標(biāo)號(hào)操作中，受影響的節(jié)點(diǎn)的距離標(biāo)號(hào)會(huì)嚴(yán)格遞增。

證明：注意到預(yù)處理步驟創(chuàng)建了有效的距離標(biāo)號(hào)，我們用歸納法假設(shè)距離函數(shù)在每次操作之前總是有效的（即滿(mǎn)足前文的C1和C2條件）。一次在邊(i,j)上的推流可能會(huì)新建一條殘量大于0反邊(j,i)，且導(dǎo)致一個(gè)新的條件? 也必須被滿(mǎn)足。此條件由推流操作自帶的屬性d(i)=d(j)+1得出，所以成立。使用邊(i,j)的推流操作可能會(huì)導(dǎo)致此邊殘量用完而從殘量網(wǎng)絡(luò)上被刪除，但這并不會(huì)影響距離函數(shù)的有效性。在重標(biāo)號(hào)操作中，節(jié)點(diǎn)i的新標(biāo)號(hào)?也總是滿(mǎn)足有效性條件。重標(biāo)號(hào)操作將執(zhí)行于沒(méi)有任何一條邊(i,j)殘量大于0且d(i)=d(j)+1時(shí)。由此得出，，命題得證，并由此引出引理2：

引理2：在預(yù)流推進(jìn)的每個(gè)中間狀態(tài)中，對(duì)于每個(gè)有正超額流的節(jié)點(diǎn)i，在殘量網(wǎng)絡(luò)上總是有一條從i到s的有向路徑。

證明：由Ford和Fulkerson提出的流結(jié)構(gòu)理論，任何預(yù)流x可以在原網(wǎng)絡(luò)G上被分解為一系列流的總和，沿著以下這些路徑：

• s到t的路徑

• s到活點(diǎn)的路徑

• 有向環(huán)

令i為一個(gè)活點(diǎn)，對(duì)應(yīng)于原圖G的預(yù)流x。由流的分解，必然存在一條從s到i的路徑，這是因?yàn)閺膕到t的路徑以及有向環(huán)不會(huì)貢獻(xiàn)節(jié)點(diǎn)i的超額流。此時(shí)反圖P在殘量網(wǎng)絡(luò)上（這里應(yīng)該是引了FF論文的定義或者結(jié)論），因此殘量網(wǎng)絡(luò)上存在一條從i到s的路徑。

推論1：對(duì)于每個(gè)節(jié)點(diǎn)?。

證明：最后一次節(jié)點(diǎn)i被重標(biāo)號(hào)時(shí)，它有正超額流，因此，殘量網(wǎng)絡(luò)中包含一條長(zhǎng)度至少為n-1的從i到s的路。由d(s)=n與條件C2可以推出?。

引理2還意味著重標(biāo)號(hào)步驟永遠(yuǎn)不會(huì)在空集上產(chǎn)生任何影響。

推論2：重標(biāo)號(hào)次數(shù)總是少于?。

證明：每次重標(biāo)號(hào)會(huì)至少將一個(gè)節(jié)點(diǎn)的標(biāo)號(hào)提高1，另外由推論1可得，不存在可以被重貼超過(guò)2n次標(biāo)號(hào)的節(jié)點(diǎn)。

推論3：飽和推流次數(shù)不會(huì)超過(guò)nm。

證明：設(shè)邊(i,j)在某步之后殘量用盡達(dá)到飽和（此時(shí)有d(i)=d(j)+1）。那么邊(i,j)不可能輸送更多的流，除非有流走反邊從j送回給i（退流，此時(shí)有 ）。而退流至少得在d(j)被拔高了至少2才可能發(fā)生。因此由推論1，邊(i,j)最多飽和n次，所以所有的邊加在一起也不會(huì)超過(guò)nm次。（注意我們假設(shè)邊(i,j)和(j,i)都在邊集A里，所以殘量網(wǎng)絡(luò)中的邊數(shù)不會(huì)超過(guò)m）

引理3：非飽和推流至多? 次。

證明：參見(jiàn)Goldberg and Tarjan (1986)。

引理4：算法隨找到最大流而終止。

證明：當(dāng)算法終止時(shí)，每個(gè)除源匯點(diǎn)外的節(jié)點(diǎn)的超額流都是0，所以最終的預(yù)流就是一個(gè)可行流。由于距離標(biāo)號(hào)一直滿(mǎn)足條件C1和C2且有d(s)=n，因此算法終止時(shí)，殘量網(wǎng)絡(luò)上不會(huì)含有從s到t的有向路徑。此條件即為經(jīng)典的Ford and Fulkerson的最大流算法的終止條件。

許多基于預(yù)流的算法，如Karzanov、Tarjan、Goldberg and Tarjan (1986)，的性能瓶頸在于非飽和推流次數(shù)。至于為何非飽和推流占得份子比飽和推流更多，部分是因?yàn)轱柡屯屏鲿?huì)刪掉殘量網(wǎng)絡(luò)中的邊，這種現(xiàn)象導(dǎo)致了飽和推流頂多需要O(nm)次，且與推流的先后順序無(wú)關(guān)。而非飽和推流不會(huì)修改殘量網(wǎng)絡(luò)的結(jié)構(gòu)，所以更難算出它的操作次數(shù)上界。Goldberg (1985) 給出在節(jié)點(diǎn)遵循先入先出序處理時(shí)，非飽和推流次數(shù)是??的。Goldberg and Tarjan (1986) 使用動(dòng)態(tài)樹(shù)來(lái)優(yōu)化了這套算法。Cheriyan and Maheshwari (1988) 證明了在每次用最高標(biāo)號(hào)的節(jié)點(diǎn)推流時(shí)，非飽和推流可以降至? 次，并且這個(gè)上界很緊。他們也證明了通用預(yù)流推進(jìn)? 和先入先出預(yù)流推進(jìn)??這倆復(fù)雜度也很緊。在下一節(jié)，我們將展示如何使用scaling（技巧名稱(chēng)，后文保留原詞不譯）來(lái)戲劇化地降低非飽和推流次數(shù)至?。

3. THE EXCESS SCALING ALGORITHM （正篇）

就是說(shuō)咱們用了一個(gè)叫做excess scaling的技巧來(lái)把預(yù)流推進(jìn)非飽和推流的次數(shù)從? 優(yōu)化到了??；舅悸肥前褤碛?strong>足夠大超額流的節(jié)點(diǎn)往足夠小超額流點(diǎn)推流，并保持這些超額流不要變得太大，咱們把這種算法叫做excess scaling algorithm（超額增量算法？）

本算法進(jìn)行??次scaling，在每次迭代中，我們定義主導(dǎo)超額流算子Δ為2的冪，是一個(gè)對(duì)所有節(jié)點(diǎn)i滿(mǎn)足??（跳前章的讀者注意，此處ei指節(jié)點(diǎn)i的超額流excess值）的最小整數(shù)。此外，每次新的scaling會(huì)令Δ減半。在一次scaling中，我們確保每次非飽和推流（沒(méi)有用完某條邊殘量的推流操作，叫非飽和推流）會(huì)推送至少Δ/2單位的流，以此來(lái)限制這個(gè)Δ不會(huì)增高。為了保證每次非飽和推流推的是至少Δ/2的流，我們只考慮超額流大于Δ/2的節(jié)點(diǎn)。在這些擁有較大超額流的節(jié)點(diǎn)中，我們選中一個(gè)擁有最小距離標(biāo)號(hào)的節(jié)點(diǎn)。這種選擇可以確保流會(huì)被推到一個(gè)擁有較小超額流的節(jié)點(diǎn)去。我們證明了頂多在? 次非飽和推流之后，Δ會(huì)降為相當(dāng)于被除了個(gè)至少2的因子，并且一個(gè)新的scaling得以開(kāi)始。在最多K次scaling操作后，所有的節(jié)點(diǎn)超額流都會(huì)降至0，至此我們可以得到最大流。

為了選中一個(gè)距離標(biāo)號(hào)最小，且擁有超過(guò)Δ/2超額流的節(jié)點(diǎn)，我們需要維護(hù)2n-1個(gè)鏈表。它們得支持O(1)的插入和刪除指定元素。我們用變量level來(lái)表示上述這些列表中，下標(biāo)值最小的非空列表的那個(gè)下標(biāo)。

我們需要一些技巧來(lái)快速選中可行邊（即滿(mǎn)足距離標(biāo)號(hào)d(i)=d(j)+1的邊，推流的前提）。對(duì)每個(gè)節(jié)點(diǎn)i我們有出邊鄰接表A(i)，這個(gè)邊的順序可以隨意，但一旦算法開(kāi)始就不得修改。對(duì)于每個(gè)節(jié)點(diǎn)i我們插入一條特殊的null邊于A(i)的尾部。然后做一下當(dāng)前弧優(yōu)化——對(duì)每個(gè)點(diǎn)i維護(hù)一個(gè)當(dāng)前弧下標(biāo)，指向一個(gè)能被i推流的候選邊。一開(kāi)始所有的當(dāng)前弧都指向這個(gè)節(jié)點(diǎn)的第一條出邊，每當(dāng)當(dāng)前弧已經(jīng)不再是一條可行邊，則令這個(gè)當(dāng)前弧指向其鄰接表中下一條邊。當(dāng)某個(gè)節(jié)點(diǎn)的邊表已經(jīng)被處理完畢時(shí)，它的當(dāng)前弧指向我們預(yù)先放好的null邊，此時(shí)這個(gè)節(jié)點(diǎn)要被重標(biāo)號(hào)，然后我們令這個(gè)點(diǎn)的當(dāng)前弧重新指向它的第一條出邊。

4. COMPLEXITY OF THE ALGORITHM

本節(jié)將證明此算法能在??的時(shí)間內(nèi)算出正確的最大流。

引理5：此excess scaling algorithm滿(mǎn)足以下兩個(gè)條件：

• C3.?每次從i到j(luò)的非飽和推流至少會(huì)傳送Δ/2單位的流量

• C4.?不會(huì)有超額流在推流后超過(guò)Δ

證明：對(duì)于每次在邊(i,j)上的推流，我們有?，這是因?yàn)辄c(diǎn)i是超額流大于Δ/2且距離標(biāo)號(hào)最小的點(diǎn)（譯注：大往小1推，如果存在j有大于Δ/2的流，由最小標(biāo)號(hào)的枚舉順序，那么它應(yīng)該會(huì)先于這個(gè)i被枚舉到，所以這個(gè)最小標(biāo)號(hào)的條件可以保證我們最先枚舉到的(i,j)一定滿(mǎn)足上述條件）。同時(shí)由推流條件，有?。因此，通過(guò)推送??單位的流，我們可以確保本次推流要么至少可以傳送Δ/2單位的流，要么用盡這條邊的容量而成為飽和推流。此外，這次推送只會(huì)增加j點(diǎn)的超額流，我們?cè)O(shè)為j點(diǎn)被推流之后的超額流，則有。所有節(jié)點(diǎn)的超額流因此會(huì)保持小于等于Δ。

當(dāng)然也有別的做法可以保證算法運(yùn)行過(guò)程中C3和C4條件總是成立，但取最小距離標(biāo)號(hào)的超額流超過(guò)Δ/2是一種簡(jiǎn)單而高效的做法。

在C3和C4條件成立的情況下，推流操作可以被視為一種restrained?greedy?approach（受限制的貪心方法）。C3保證了從i到j(luò)的推流足夠大而有效，C4保證了每次迭代不會(huì)有超額流超過(guò)Δ。特別地，節(jié)點(diǎn)i會(huì)留一些余地防止j的超額流超過(guò)Δ，而不是貪心地一股腦把自己的超額流全往人家身上推。保持最大超額流更低可能在實(shí)踐和理論中更有用。它的主要影響是鼓勵(lì)超額流能夠在網(wǎng)絡(luò)中分布得更平均，而這種分布應(yīng)該可以令中間節(jié)點(diǎn)往匯點(diǎn)更容易地推流。這可能很重要，出于如下考慮：我們?cè)O(shè)想若干個(gè)點(diǎn)往j點(diǎn)推流使得j點(diǎn)的超額流非常大，此時(shí)j點(diǎn)不太能夠把它的流往離匯點(diǎn)更近的地方推，在這種情況下，j點(diǎn)不得不重標(biāo)號(hào)，使得它的標(biāo)號(hào)增高，并且大多超額流得返還回去。我們可以維護(hù)C4條件從而避免這種“打太極”現(xiàn)象。

引理6：如果每次推流都滿(mǎn)足條件C3和C4，那么非飽和推流在每次scaling中最多有? 次。

證明：考慮勢(shì)函數(shù)?。F的初始值在一次scaling中上界是?，因?yàn)閑i上界是Δ，而d(i)上界是2n。在算法處理節(jié)點(diǎn)i的時(shí)候，以下兩個(gè)情況之一必發(fā)生：

情況1：找不到任何能推流的邊，這種情況在i點(diǎn)的當(dāng)前弧到達(dá)A(i)尾部時(shí)發(fā)生。觀(guān)察到如果一條邊(i,j)已經(jīng)是不再是可行邊，那么它在d(i)被提高之前一直都不會(huì)是可以推流的可行邊，因?yàn)閐(j)是非遞減的。因此，當(dāng)i點(diǎn)不再有對(duì)外的可行邊時(shí)，重標(biāo)號(hào)會(huì)給d(i)提高至少1個(gè)單位，我們令提高的高度為ε，則F至多增加ε。對(duì)于所有的點(diǎn)i，由于d(i)在整個(gè)算法流程中不會(huì)提高超過(guò)2n個(gè)單位，所以在一次scaling迭代中，節(jié)點(diǎn)重標(biāo)號(hào)給F帶來(lái)的增量不會(huì)超過(guò)?。（實(shí)際上把所有的scaling加一起，F(xiàn)的增量也不會(huì)超過(guò)?）

情況2：找到了一條可以推流的可行邊，推流有飽和和不飽和兩種情況。在這兩種情況下F都會(huì)減少。邊(i,j)的非飽和推流會(huì)傳送至少Δ/2的流量，由于d(j)=d(i)-1，這個(gè)操作會(huì)使F減少至少1/2個(gè)單位。因?yàn)橐淮蝧caling中F的初值加上F的增量總和不會(huì)超過(guò)??，這種情況不會(huì)發(fā)生超過(guò)? 次。

定理1：scaling算法進(jìn)行? 次非飽和推流。

證明：Δ的初值是? 。由引理6，Δ將在至多??次的非飽和推流之后減半，并開(kāi)始新一次迭代。在??次scaling后，Δ<1，此時(shí)由于s、t之外的點(diǎn)超額流都是0，算法得以得到一個(gè)可行流，且由引理4知此可行流即為最大流。

定理2：excess scaling algorithm的復(fù)雜度是?。

證明：此算法的復(fù)雜度由main中while的執(zhí)行次數(shù)決定。每次循環(huán)中，要么觸發(fā)一次對(duì)i點(diǎn)的推流或者重標(biāo)號(hào)操作，要么變量level會(huì)增加。每次推流或重標(biāo)號(hào)有以下兩種情況：

情況1：推流被觸發(fā)，其中飽和推流O(nm)次，非飽和推流??次，這種情況發(fā)生??次。

情況2：i的標(biāo)號(hào)被提高。由推論1，這種情況對(duì)每個(gè)節(jié)點(diǎn)O(n)次，加起來(lái)一共??次。

因此算法會(huì)調(diào)用推流/重標(biāo)號(hào)??次。我們需要在O(1)時(shí)間內(nèi)找到一條邊進(jìn)行推流?？紤]更新當(dāng)前弧，在|A(i)|次迭代枚舉完i點(diǎn)的邊之后，情況2會(huì)發(fā)生，此時(shí)i點(diǎn)的標(biāo)號(hào)會(huì)增高。因此，總開(kāi)銷(xiāo)是??再加上推流/重標(biāo)號(hào)操作的開(kāi)銷(xiāo)，顯然他們之和是?。

（譯注：雖然我覺(jué)得在文初無(wú)重邊的假設(shè)下，|A(i)|應(yīng)該是O(n)，而不是O(m)的）

接著我們考慮重標(biāo)號(hào)操作的時(shí)間開(kāi)銷(xiāo)。計(jì)算點(diǎn)i的新距離標(biāo)號(hào)需要遍歷i的所有出邊A(i)，從而總計(jì)需要??的時(shí)間來(lái)完成所有的重標(biāo)號(hào)操作。由于鏈表LIST(r)使用鏈接棧以及隊(duì)列實(shí)現(xiàn)（咱們代碼中還是老實(shí)手寫(xiě)了個(gè)雙向鏈表），因此增加和刪除一個(gè)任意元素是O(1)的。所以說(shuō)更新這些鏈表不是復(fù)雜度的瓶頸。

最后，我們需要算出level的增加次數(shù)上限。在每次scaling迭代中，level的上界是2n-1，下界是1。因此，每次scaling中l(wèi)evel的增加次數(shù)是它降低次數(shù)+2n。此外，level降低只可能發(fā)生在一次推流發(fā)生后，并且只是降1,。因此把所有的scaling操作加起來(lái)，它的增加次數(shù)是推流次數(shù)+?，所以總的還是??的。

5. REFINEMENTS

一些魔改可能可以提高本算法的實(shí)際運(yùn)行效率而不會(huì)影響最壞情況下的復(fù)雜度，哥們說(shuō)三種改法：

1. 修改scale factor。

2. 允許小部分非飽和推流。

3. 嘗試尋找不與匯點(diǎn)連通的點(diǎn)。（省流：global_relabel和gap優(yōu)化）

第一是考慮scale factor怎么改，上邊的算法用的是2，即每次循環(huán)完令Δ變?yōu)棣?2。實(shí)際運(yùn)行中，某些固定的整數(shù)scale factor??可以得到更好的結(jié)果。此時(shí)主導(dǎo)超額流算子Δ是最小的滿(mǎn)足所有點(diǎn)的超額流不大于它的β的冪。且條件C3變更如下：

C3'. 每次i到j(luò)的非飽和推流傳送至少Δ/β單位的流。

前面說(shuō)的scaling算法可以小改以適配這個(gè)新的因子β，我們令??？梢宰C明此時(shí)的魔改算法復(fù)雜度是?。以最壞情況去考慮，任何固定的β值都是最優(yōu)的。實(shí)踐中應(yīng)該靠經(jīng)驗(yàn)去調(diào)這個(gè)超參。

第二是考慮非飽和推流怎么推。我們前面說(shuō)的算法是選中??的點(diǎn)進(jìn)行非飽和或者飽和推流。其實(shí)我們也可以一直把這個(gè)點(diǎn)的流往外推，直到我們用完它的超額流或者推了一次至少Δ/2的非飽和流。這個(gè)修改可能會(huì)產(chǎn)生更多的來(lái)自i點(diǎn)的飽和推流甚至允許i點(diǎn)在流量低于Δ/2時(shí)仍進(jìn)行推流。另一方面，前述的算法每次非飽和推流至少要推Δ/2，其實(shí)如果對(duì)于某個(gè)大于等于1的常量r，你能保證每r次非飽和推流能傳送Δ/2單位的流量的話(huà)，你也能達(dá)成同樣的復(fù)雜度。

第三是考慮實(shí)際運(yùn)行中重標(biāo)號(hào)導(dǎo)致的瓶頸。特別地，當(dāng)d(i)超過(guò)n-2時(shí)，本算法可以得出此時(shí)在殘量網(wǎng)絡(luò)上已經(jīng)不再有從i到t的路徑。Goldberg (1987) 建議偶爾進(jìn)行bfs掃描以讓距離標(biāo)號(hào)正確可能很有用（global_relabel操作），實(shí)際上這么做確實(shí)跑得飛快。

一個(gè)可選的辦法是記? 為標(biāo)號(hào)為k的點(diǎn)數(shù)，如果某次重標(biāo)號(hào)中一個(gè)標(biāo)號(hào)為k的點(diǎn)被拔高導(dǎo)致??變0，則在殘量網(wǎng)絡(luò)上這些標(biāo)號(hào)大于k的點(diǎn)不可能再與匯點(diǎn)連通。（一旦點(diǎn)j與匯點(diǎn)不再連通，它直到從j到t的基于長(zhǎng)度的最短路是非遞減時(shí)為止都會(huì)保持不連通。）我們避免選中這些點(diǎn)直到所有正超額流點(diǎn)都與匯點(diǎn)斷開(kāi)為止。此時(shí)多出來(lái)的超額流應(yīng)該還給源點(diǎn)（不然得到的殘量網(wǎng)絡(luò)不對(duì)）。根據(jù)這個(gè)思想我們可以把算法設(shè)計(jì)成兩個(gè)階段，階段1用預(yù)流（可以得到最大流的值），階段2把預(yù)流轉(zhuǎn)換成可行的最大流（可以得到殘量網(wǎng)絡(luò)，從而得到最小割的選邊方案）。

（譯注：如果只是需要最大流值，則沒(méi)必要把階段1之后其余點(diǎn)的超額流返還給源點(diǎn)，可以見(jiàn)networkx的preflow_push方法的value_only選項(xiàng)）

第六節(jié)的并行計(jì)算實(shí)現(xiàn)和第七節(jié)的相關(guān)研究這里視反饋可能打算新開(kāi)一章來(lái)翻或者咕掉。

這里放點(diǎn)干貨，以下上文提到的算法的代碼實(shí)現(xiàn)均魔改自github.com/touqir14/MaxFlow/

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

洛谷最小割樹(shù)板題P4897：https://www.luogu.com.cn/record/99812219

使用預(yù)流推進(jìn)做的最小割樹(shù)：https://www.luogu.com.cn/record/99006782

隨機(jī)圖上分別以hlpp、excess scaling、dinic作為最小割樹(shù)的最大流提供算法的運(yùn)行時(shí)間比較（dinic取自洛谷題解區(qū)，hlpp取自模板題運(yùn)行時(shí)間最短的程序）：

文末提醒一下打競(jìng)賽的后輩，不要一味追求模板的運(yùn)行效率，在賽場(chǎng)上應(yīng)該優(yōu)先選擇碼量少，打得快，修得快，跑得過(guò)的模板。ahuja_orlin的碼量（至少在這份代碼實(shí)現(xiàn)中）不小，帶來(lái)的性能優(yōu)化也比較有限。我的評(píng)價(jià)是它不適合在賽場(chǎng)上使用。如果你在找一份短小精悍的hlpp的話(huà)可以看看：https://github.com/kth-competitive-programming/kactl/blob/main/content/graph/PushRelabel.h

最后希望這篇論文翻譯能夠給在尋找有代碼實(shí)現(xiàn)的網(wǎng)絡(luò)流算法研究者一些幫助。

PS1：我試過(guò)給那份代碼加當(dāng)前弧優(yōu)化，結(jié)論是跑得更慢了

PS2：我試過(guò)把那份代碼的鄰接表改為單維vector，結(jié)論是跑得更慢了