算法學習之路|網絡流之最大流

最大流可以看做是把一些東西從源點s送到彙點t，可以從其他的點中轉，每條邊最多隻能輸送一定的物品，求最多可以把多少東西從s送到t，這樣的問題就是最大流問題。

節點1為源點，節點5位彙點

每一條邊上的數字即為這條邊最多能輸送的數量，也稱為容量。（對于不存在的邊，容量為0）

這個圖能夠求出的最大流為24。

這時，實際運送的物品量即為流量。

有些邊的流量不一定等于容量，也就是還可以在這條路上再流多幾個物品，這時，容量減去流量的值，即為殘量

殘量會單獨構成網絡，但不一定聯通s和t，這樣的網絡稱作殘量網絡。

那麼，應該怎麼求最大流呢？

這裡介紹一個最基礎的算法，增廣路算法。

在圖上，從s開始，任意取一條路來走，走到t，增加流量。重複這樣的操作。但是很快，我們可以發現，這樣的做法不一定是最優的做法。是以，我們要給它一個改進的機會。

在圖上建立反向弧，将容量設定為0，當從節點u流向節點v時，反向弧的流量也相應等于這條弧的流量的相反數。

那麼，通過搜尋，每一次尋找一條路徑，使得流向彙點的總流量增加，這個過程叫做增廣，走過的路為增廣路。

可以證明，通過這個過程，經過多次的增廣，必然會陷入不能增廣的情況，這時，流向彙點的總流量即為最大流。

隻要殘量網絡中s和t是連通的，必然會得到一條增廣路徑。

找路徑最簡單的辦法就是用DFS，但是對于一些具有刁鑽資料的網絡流題目，DFS可能會空間溢出或者逾時，是以使用到BFS，也就是題目中說的Edmonds-Karp算法。

代碼模闆（來自算法競賽入門第二版（劉汝佳））：