1、最大流最小割默認分類2010-06-20 15:39:10閱讀293評論0 字號：大中小訂閱最大流問題最大流問題是一類極為廣泛的問題。不僅在交通運輸網(wǎng)絡中有人流、車流、貨物流、供水網(wǎng)絡中有 水流、金融系統(tǒng)中有現(xiàn)金流、通訊網(wǎng)絡中信息流.等。五十年代，F(xiàn)ord(福特)、Fulkerson(富克遜)建立 的“網(wǎng)絡流理論”，是網(wǎng)絡應用的重要組成部分。網(wǎng)絡與流的概念對于有向圖D=(V,A)，如果V中有一發(fā)點vs (亦稱源還有一收點(亦稱為匯)記為vt其余均為中間 點，且對A中的每條弧均有權(quán)W(vi,vj)?0 (簡記為Wij，并稱為弧容量)，則稱這樣的賦權(quán)有向圖D為容 量網(wǎng)絡，記為D=(V,A,W)。通

2、過D中弧(vi,vj)的物流量fij，稱為弧(vi,vj)的流量。所有弧上流量的集合f=(fij 稱為該網(wǎng)絡D的一個流。最大流最小截量定理：任一網(wǎng)絡D中，最大流的流量=最小截集的截量。最大流算法的鄰接陣實現(xiàn)最大流最小割定理介紹：把一個流網(wǎng)絡的頂點集劃分成兩個集合S和T，使得源點s GS且匯點t UT，割(S,T)的容量C(S,T) =ZCuv,其中 UGS 且 veTo從直觀上看，截集(S,T)是從源點s到匯點t的必經(jīng)之路，如果該路堵塞則流從s無法到達to于是我 們可以得到下面的定理：最大流最小割定理：任意一個流網(wǎng)絡的最大流量等于該網(wǎng)絡的最小的割的容量。這個定理的證明這里就不給出了，可以參考圖

3、論方面的資料。求最大流的Edmonds-Karp算法簡介：若給定一個可行流F=(Fij)，我們把網(wǎng)絡中使Fij=Cij的弧稱為飽和弧，F(xiàn)ijCij的弧稱為未飽和弧。如 果流網(wǎng)絡中從i到?jīng)]有弧，我們添加一條從i到且容量Cij=0的弧，這樣整個流網(wǎng)絡變成一個完全圖。 如果從i到有流量Fij，則從j到i的流量定義為Fji = -Fij o考慮一條從源點s出發(fā)到匯點t的路徑p，如 果對于每一段弧(i,j)屬于p都有Fij Cij，即每一條屬于p的弧都是未飽和弧，則我們可以向這條路徑上壓 入更多的流，使得其中的一條弧達到飽和。這樣的路徑p叫做可改進路，可壓入的流量叫做該可改進路的 可改進流量。重復這個過

4、程，直到整個網(wǎng)絡找不到一條可改進路，顯然這時候網(wǎng)絡的流量達到最大。 Edmonds-Karp算法就是利用寬度優(yōu)先不斷地找一條從s到t的可改進路，然后改進流量，一直到找不到 可改進路為止。由于用寬度優(yōu)先，每次找到的可改進路是最短的可改進路，通過分析可以知道其復雜度為 O(VE2)oEdmonds-Karp算法的偽代碼如下：設隊列Q-存儲當前未檢查的標號點，隊首節(jié)點出隊后，成為已檢查的標點；path -存儲當前已標號可改進路經(jīng);repeatpath置空；源點s標號并進入path和Q;while Q非空and匯點t未標號dobegin移出Q的隊首頂點u;for每一條從u出發(fā)的弧(u,v) doif

5、v未標號and弧(u,v)的流量可改進then v進入隊列Q和path;end whileif匯點已標號then從匯點出發(fā)沿著path修正可改進路的流量；until 匯點未標號;Edmonds-Karp算法有一個很重要的性質(zhì)：當匯點未標號而導致算法結(jié)束的時候，那些已經(jīng)標號的節(jié) 點構(gòu)成集合S，未標號的節(jié)點構(gòu)成集合T，割(S,T)恰好是該流網(wǎng)絡的最小割；且這樣求出的最小割(S,T)中 集合S的元素數(shù)目一定是最少的。尋找最大流的基本方法是Ford-Fulkerson方法，該方法有多種實現(xiàn)，其基本思想是從某個可行流F 出發(fā)，找到關(guān)于這個流的一個可改進路經(jīng)P，然后沿著P調(diào)整F，對新的可行流試圖尋找關(guān)于他

6、的可改進 路經(jīng)，如此反復直至求得最大流?，F(xiàn)在要找最小費用的最大流，可以證明，若F是流量為V(F)的流中費用 最小者，而P是關(guān)于F的所有可改進路中費用最小的可改進路，則沿著P去調(diào)整F,得到的可行流F一定是 流量為V(F)的所有可行流中的最小費用流。這樣，當F是最大流時候，他就是所要求的最小費用最大流。注意到每條邊的單位流量費用B(i,j)0，所以F=0必是流量為0的最小費用流，這樣總可以從F=0 出發(fā)求出最小費用最大流。一般的，設已知F是流量V(F)的最小費用流，余下的問題就是如何去尋找關(guān)于 F的最小費用可改進路。為此我們將原網(wǎng)絡中的每條弧u,v變成兩條方向相反的?。?。前向弧u,v，容量C和費

7、用B不變，流量F為0；2。后向弧v,u，容量C為0，費用為-B，流量F為0；每一個頂點上設置一個參數(shù)CT，表示源點至該頂點的通路上的費用和。如果我們得出一條關(guān)于F的 最小費用可改進路時，則該路上的每一個頂點的CT值相對于其它可改進路來說是最小的。每一次尋找最 小費用可改進路時前，源點的CT為0,其它頂點的CT為+8。設cost為流的運輸費用，初始時由于F=0,則cost=0,我們每求出一條關(guān)于F的最小費用可改進路， 則通過cost cost + ZB(e)*d,(其中eP,d為P的可改進量)來累積流的運輸費用的增加量。顯然，當求出最小費用最大流時，cost便成為最大流的運輸費用了。另外設置布爾

8、變量break為最小費用可改進路的延伸標志，在搜索了網(wǎng)絡中的每一個頂點后，若 break=true表示可改進路還可以延伸，還需要重新搜索網(wǎng)絡中的頂點；否則說明最小費用的可改進路已經(jīng) 找到或者最大流已經(jīng)求出。這個模版的代碼完全按照BFS從源點逐個遍歷增廣路徑，得到最大增廣容量，通過不斷調(diào)整，最后求得 最大流量,值得注意的是，最后一次BFS后所標的路線即為最小截集，即所謂的瓶頸，據(jù)此很容易求出最小截 集的容量。#include #include using namespace std;鄰接陣實現(xiàn)const long MAXN=1000;const long lmax=0 x7FFFFFFF;lon

9、g NetMAXNMAXN;/殘 余網(wǎng)絡long PathMAXN;/ 增廣路徑long LvMAXN;/增廣路徑通過容量queue q;long m,n;/ 點，邊long Start,End;void init()while (!q.empty()q.pop();memset(Path,-1,sizeof(Path);Lg M. ,long b)return ab?a:b;L W)init();PathStart=0;LvStart=lmax;q.push(Start);while (!q.empty()long t=q.front();q.pop();if (t=End)(break;l

10、ong i;for (i=1；i=m;+i)(if (i!=Start&Pathi=-1&Netti)(Lvi=Min(Lvt,Netti);q.push(i);Pathi=t;if (PathEnd=-1)(return -1;return Lvm;void print(long n)(printf(%ldn,n);void Ford_Fulkerson()(long i;long Max_Flow=0;for (i=0;in;+i)(long from,to,cost;scanf(%ld %ld %ld”,&from,&to,&cost);Netfromto=cost;/cost 為剩余量

11、如果在現(xiàn)有網(wǎng)絡上擴展剩余量為容量-已占用量最大流結(jié)果要加上已流入的量scanf(%ld %ld”,&Start,&End);long step;while (step=bfs()!=-1)/反搜增廣路徑并調(diào)整流量(Max_Flow+=step;long now=End;while (now!=Start)(long pre=Pathnow;Netprenow-=step;Netnowpre+=step;now=pre;print(Max_Flow);int main()(while (scanf(%ld %ld,&m,&n)!=EOF)(Ford_Fulkerson();return 0;經(jīng)常

12、看見論文里面提到max flow/min cut theory，總是不太明白，今天花了點時間好好學習了一下， 發(fā)現(xiàn)其實也就挺簡單的兩概念。首先說說什么是流(flow)在一個有向圖中，只有出去的邊沒有進來的邊的節(jié)點叫做源(source)，只有進來的邊沒有出去的邊的節(jié) 點叫做匯(sink)，其它的節(jié)點進來的邊和出去的邊應該是平衡的。邊上可以加權(quán)值，假設對于一個交通圖來說，可以認為邊上的權(quán)重為一條道路上的最大流量。那么對于 圖中任意兩個節(jié)點來說，他們之間可以存在多條路徑，每條路徑上可以負載的最大流量應該是這條路徑上 權(quán)重最小的那條邊所能承載的流量(聯(lián)想一下“瓶頸”這個詞，或者木桶理論)。那么所有的路徑上所負載 流量之和也就是這兩個節(jié)點之間所能通過的最大流了(max flow)。Ford和Fulkerson的算法很簡單，把兩個節(jié)點之間所有路徑找到，然后.很直觀，很簡單。不知 道這么簡單的算法怎么就用他們的名字命名了，明顯誰都想得到的。此外，介紹一下什么是割。對于一個圖中的兩個節(jié)點來說，如果把圖中的一些邊去掉，剛好讓他們之 間無法連通的話，這些被去掉的邊組成的集合就叫做割了。最小割就是指所有割中權(quán)重之和最小的一個割。OK，現(xiàn)在開始進入正題，其實很easy。最大流-最小割定理(max flow/min cut theory):對于任意一個只有一個源和一個匯的圖來