網絡流問題

很多問題都可以轉化成網絡流問題，如運輸貨物時的物流問題，水流問題，匹配問題等等。網絡是一個各條邊都有權值和方向的圖。

網絡流問題，一般情況下我們會把各種網絡問題抽象成網絡流問題，網絡流是滿足以下性質的網絡：每一條邊擁有一個最大的容量c，即該條邊可以容納的最大流量，f是流過該邊的實際流量，且總有f<=c。對於頂點（源點和匯點除外）都有流出的流量等於流入的流量。一個源點一個匯點，且對於源點來説其流入量為0，對於匯點來説流出量為0，源點的流出量等於匯點的流入量，對於最大流問題既是要找出流入匯點的最大流量值 ^[1]  。

問題表述：給定一幅圖（n個結點，m條邊），每一條邊有一個容量，需要將一些物品從結點s（稱為源點）運送到結點t（稱為匯點），可以從其他結點中轉，求最大的運送量。

在介紹最大流問題的解決方法之前，先介紹幾個概念：反向弧，殘餘網絡，增廣路徑，最大流定理。

反向弧：若從u到v的邊的容量為c ，這條邊上有流量 f 流過（稱為正向弧），則相當於v到u有一條容量為0的邊，其流量為- f ，這條邊就是反向弧。

反向弧的意義：反向弧的作用是起到有更優決策的時候會使當前選擇的弧會自動放棄。反向弧有流量的原因是因為如果剛剛選擇了正向弧，下一次如果存在更優策略使這f的流量流入匯點，就可以選擇反向弧，將流量 f 撤銷。

殘餘網絡：計算出圖中的每條邊上容量與流量之差（稱為殘餘容量），即可得到殘餘網絡。注意由於反向邊的存在，殘餘網絡中的邊數可能到達原圖中邊數的兩倍。

舉例如下：觀察圖1，這種狀態下它的殘餘網絡如圖2所示。

增廣路徑：殘餘網絡中任何一條從s到t的有向道路都對應一條原圖中的增廣路徑 —— 只要求出該道路中所有殘量的最小值d ，把對應的所有邊上的流量增加d 即可，這個過程稱為增廣。

最大流定理：如果殘留網絡上找不到增廣路徑，則當前流為最大流；反之，如果當前流不為最大流，則一定有增廣路徑。

這樣的話，求解最大流就只需要在殘餘網絡中尋找增廣路，直到不存在可以從s流向t 的增廣路，此時即為最大流。求解最大流問題的高效算法有 dinic,sap和isap。

割：將圖1中所有頂點分成兩個集合S和 T = V - S ，其中源點s在集合S中，匯點t在集合T中。如果把 ” 起點在S中，終點在T中的邊全部刪除，就無法從s到達 t了。這樣的集合劃分（S,T）稱為一個割，它的容量定義為：∑(邊( u , v )的容量和)，其中 u ∈ S , v ∈ T ，即起點在 S 中，終點在 T 中的所有邊的容量和。（這裏所有的邊都不包括反向弧）

最小割：圖1中所有的割中，邊權值和最小的割為最小割。

最小割最大流定理：最大流的值為最小割的容量！

如何求最小割：求完最大流後，在殘留網絡中從源點 s 開始 dfs ，將能到達的點標號（ c - f >0 的邊），已標號結點的集合為S，未標號結點集合為 T，則邊集[ S , T ]為最小割。

定理證明：

從s運送到t的物品必然通過跨越S和T的邊，所以從s到t的淨流量等於|f|=f（S,T）=∑f（u，v）≤∑c（u，v）=c（S,T）。(u∈S, v∈T)

注意這裏的割（S,T）是任取的，因此得到了一個重要的結論：對於任意s-t流和任意s-t割（S,T）,有|f|≤c（S,T）。

下面來看殘餘網絡中沒有增廣路的情形。既然不存在增廣路，在殘餘網絡中s和t並不連通。當BFS沒有找到任何s-t道路，把已標號結點集合看成S，令T=V-S，則在殘餘網絡中S和T分離，因此在圖1中跨越S和T的所有弧滿載（這樣的邊才不會存在於殘餘網絡中），且沒有從T回到S的流量，因此|f|= c（S,T）成立。

前面説過，對於任意的f和（S,T），都有|f|≤c（S,T）,而此處又找到了一組讓等號成立的f和（S,T）。這樣便證明了最小割最大流定理。

在保證最大流的情形下，網絡中的邊，可能不只有流量還有費用，那麼如果我們一方面希望網絡擁有最大流，另一方面我們要求費用達到最小，這就是一個費用流的問題了，對於費用流的問題，事實上我們可以這麼考慮，首先我們必須要找到的是最大流，另一方面我們需要費用最小，而在找最大流的時候我們總是在尋找增廣路來增廣，來使得我們能得到一個更大的流，那麼另一方面要求費用最小，所以我們可以在尋找增廣路的時候找一條費用最小路來增廣，而費用我們也可以看成是距離類的東西，也就是這樣的話，我們可以用最短路，來找出這樣一個最小費用的路來進行增廣，而不斷增廣，即可得到最大流，這樣我們就可以得到最小費用最大流。

網絡流和費用流中經常會涉及到拆點的操作，將一個點分成入和出，來拆成兩個點。例如聯合訓練賽的第六場第一個題目tour，給出一張圖，要求將這個圖劃分成幾個集合，要求每個集合的點的個數大於等於2，要求這個集合所有點可以構成一個環。圖中的每條邊都有一個邊權，最後找到各個集合的總花費為所有構成環的邊的權之和。要求這個花費最小 ^[2]  。