資料結構之網絡流入門(Network Flow)簡單小節

網絡流的相關定義： 源點：有n個點，有m條有向邊，有一個點很特殊，隻出不進，叫做源點。 彙點：另一個點也很特殊，隻進不出，叫做彙點。 容量和流量：每條有向邊上有兩個量，容量和流量，從i到j的容量通常用c[i,j]表示,流量則通常是f[i,j]. 通常可以把這些邊想象成道路，流量就是這條道路的車流量，容量就是道路可承受的最大的車流量。很顯然的，流量<=容量。而對于每個不是源點和彙點的點來說，可以類比的想象成沒有存儲功能的貨物的中轉站，所有“進入”他們的流量和等于所有從他本身“出去”的流量。 最大流：把源點比作工廠的話，問題就是求從工廠最大可以發出多少貨物，是不至于超過道路的容量限制，也就是，最大流。

求解思路： 首先，假如所有邊上的流量都沒有超過容量(不大于容量)，那麼就把這一組流量，或者說，這個流，稱為一個可行流。 一個最簡單的例子就是，零流，即所有的流量都是0的流。 (1).我們就從這個零流開始考慮，假如有這麼一條路，這條路從源點開始一直一段一段的連到了彙點，并且，這條路上的每一段都滿足流量<容量，注意，是嚴格的<,而不是<=。 (2).那麼，我們一定能找到這條路上的每一段的(容量-流量)的值當中的最小值delta。我們把這條路上每一段的流量都加上這個delta，一定可以保證這個流依然是可行流，這是顯然的。 (3).這樣我們就得到了一個更大的流，他的流量是之前的流量+delta，而這條路就叫做增廣路。我們不斷地從起點開始尋找增廣路，每次都對其進行增廣，直到源點和彙點不連通，也就是找不到增廣路為止。 (4).當找不到增廣路的時候，目前的流量就是最大流，這個結論非常重要。 補充： (1).尋找增廣路的時候我們可以簡單的從源點開始做BFS，并不斷修改這條路上的delta 量，直到找到源點或者找不到增廣路。 (2).在程式實作的時候，我們通常隻是用一個c 數組來記錄容量，而不記錄流量，當流量+delta 的時候，我們可以通過容量-delta 來實作，以友善程式的實作。

相關問題： 為什麼要增加反向邊？ 在做增廣路時可能會阻塞後面的增廣路，或者說，做增廣路本來是有個順序才能找完最大流的。 但我們是任意找的，為了修正，就每次将流量加在了反向弧上，讓後面的流能夠進行自我調整。

舉例： 比如說下面這個網絡流模型

我們第一次找到了1-2-3-4這條增廣路，這條路上的delta值顯然是1。 于是我們修改後得到了下面這個流。（圖中的數字是容量）

這時候(1,2)和(3,4)邊上的流量都等于容量了，我們再也找不到其他的增廣路了，目前的流量是1。 但是， 這個答案明顯不是最大流，因為我們可以同時走1-2-4和1-3-4，這樣可以得到流量為2的流。

那麼我們剛剛的算法問題在哪裡呢？ 問題就在于我們沒有給程式一個“後悔”的機會，應該有一個不走(2-3-4)而改走(2-4)的機制。 那麼如何解決這個問題呢？ 我們利用一個叫做反向邊的概念來解決這個問題。即每條邊(i,j)都有一條反向邊(j,i)，反向邊也同樣有它的容量。 我們直接來看它是如何解決的： 在第一次找到增廣路之後，在把路上每一段的容量減少delta的同時，也把每一段上的反方向的容量增加delta。