最大流算法（課堂PPT）

1、1網(wǎng)絡(luò)流初步網(wǎng)絡(luò)流初步2 最大流算法最大流算法 最小費(fèi)用最大流最小費(fèi)用最大流 最大流最小割定理最大流最小割定理3最大流算法最大流算法網(wǎng)絡(luò)流之一網(wǎng)絡(luò)流之一4 問題：問從S到T的最大水流量是多少？ 1 S43256 t7 3484246實(shí)例： 有一自來水管道輸送系統(tǒng)，起點(diǎn)是S，目標(biāo)是T，途中經(jīng)過的管道都有一個最大的容量。5 1 S43256 t7 348424646222446最大水流量是106一、網(wǎng)絡(luò)流的定義 有唯一的一個源點(diǎn)S（入度為0：出發(fā)點(diǎn)） 有唯一的一個匯點(diǎn) T（出度為0：結(jié)束點(diǎn)） 圖中每條弧 (u, v) 都有一非負(fù)容量 c ( u, v )有向圖 G = ( V, E )中：滿足上述

2、條件的圖G稱為網(wǎng)絡(luò)流圖。記為： G = ( V, E ，C)71、可行流每條弧 ( u, v )上 給定一個實(shí)數(shù)f(u,v),滿足：有 0 = f ( u, v ) = c( u, v ),則f(u,v)稱為弧( u, v )上的流量。如果有一組流量滿足條件： 源點(diǎn)s ： 流出量 = 整個網(wǎng)絡(luò)的流量 匯點(diǎn)t ： 流入量 =整個網(wǎng)絡(luò)的流量 中間點(diǎn)：總流入量 = 總流出量 那么整個網(wǎng)絡(luò)中的流量成為一個可行流。區(qū)分：容量和流量8124356423454121243542333112435642345411243542353334一個可行流：5一個可行流：7圖1圖292、最大流 在所有的可行流中， 流

3、量最大的一個流的流量 如： 圖2中可行流7也是最大流。 最大流可能不只一個。10二、最大流算法二、最大流算法步驟：（1）如果存在增廣路徑,就找出一條增廣路徑 （2）然后沿該條增廣路徑進(jìn)行更新流量 （增加流量）Ford-Fulkerson （福特-?？松┧惴ǎ?11、增廣路徑、增廣路徑 從從 s 到到 t 的一條簡單路徑，若邊的一條簡單路徑，若邊 ( u, v ) 的方向與的方向與該路徑的方向一致，稱該路徑的方向一致，稱 ( u, v ) 為正向邊，方向不為正向邊，方向不一致時(shí)稱為逆向邊。一致時(shí)稱為逆向邊。簡單路：簡單路：13 245中。中。（1，3）（）（2，4）（4，5）是正向邊。（是正向

4、邊。（3，2）是逆向邊。）是逆向邊。124356423451243564234512若路徑上所有的邊滿足：若路徑上所有的邊滿足：所有正向邊有：所有正向邊有：f ( u, v ) c ( u, v) f ( u, v ) 0f ( u, v ) 0則稱該路徑為一條則稱該路徑為一條增廣路徑增廣路徑( (可增加流量可增加流量) )增廣路徑：兩條增廣路徑：兩條增廣路徑：13513 2451243564234522212435642345222增加流量增加流量=？132、沿增廣路徑增廣、沿增廣路徑增廣 1） 先設(shè)d為為正無窮(可增加流，余流量) 若( u, v ) 是正向邊 d = min ( d, c

5、 ( u, v ) f (u, v ) ) 若( u, v ) 是逆向邊 d = min ( d, f ( u, v ) ) 2 ） 對與該增廣路徑上的邊 若( u, v ) 是正向邊，f ( u, v ) = f ( u, v ) + d; 若( u, v ) 是逆向邊，f ( u, v ) = f ( u, v ) d; 增廣后，總流量增加了d1412435642345樣例：樣例：開始流量為開始流量為:sum=0151、一條增廣路徑、一條增廣路徑: 1235d=min4,2,4 =2 增加流量增加流量: 2Sum=21243564234522212435642345162、一條增廣路徑、一

6、條增廣路徑: 1245d=min4-2,3,5 =2 增加流量增加流量: 2Sum=2+2=41243564234522212435642345222124356423452221712435642345222124356423452221243564234522-1=1212435423452223、一條增廣路徑、一條增廣路徑: 1 2 4 5d=min6,2,3-2,5-2 =1 增加流量增加流量: 1Sum=4+1=51112-3減少，加到減少，加到-3減的由減的由-補(bǔ)充補(bǔ)充184、一條增廣路徑、一條增廣路徑: 1 5d=min6-1,4-2 =2 增加流量增加流量: 2Sum=5+2=

7、71243564234522-1=121243542342221111243564234522-1=1212435423452221112219 定理： 可行流 f 為最大流，當(dāng)且僅當(dāng)不存在關(guān)于f 的增廣路徑 證：若 f 是最大流，但圖中存在關(guān)于 f 的增廣路徑，則可以沿該增廣路徑增廣，得到的是一個更大的流，與f 是最大流矛盾。所以，最大流不存在增廣路徑。20Ford-Fulkerson方法(增廣流)求最大流 （福特-福克森）步驟：（1）如果存在增廣路徑,就找出一條增廣路徑 DFS,BFS（2）然后沿該條增廣路徑進(jìn)行更新流量 （增加流量）While 有增廣路徑 do 更新該路徑的流量迭代算法2

8、1c u, v ：容量：容量f u, v ：流量：流量Bi：保存找到的增廣路徑，記錄路徑上結(jié)點(diǎn)：保存找到的增廣路徑，記錄路徑上結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)。的前驅(qū)結(jié)點(diǎn)。Sum：最大流量。：最大流量。假定：假定：1是源點(diǎn)是源點(diǎn)S；n是匯點(diǎn)是匯點(diǎn)T。算法的實(shí)現(xiàn)：22function findflow(k:integer):boolean; 找結(jié)點(diǎn)k的后繼結(jié)點(diǎn)i var i:integer; begin if k=n then exit(true); 找到了一條增廣路徑 for i:=1 to n do if(bi=-1) and(ck,i-fk,i0)or(fi,k0) then begin bi:=k; i

9、f findflow(i) then exit(true); end; exit(false); end;1）：DFS找增廣路徑232） procedure addflow;/沿增廣路徑增廣（增加流量） d:=maxint; 增量 i:=n; 沿增廣路徑的終點(diǎn)向起點(diǎn)反向求d while bi0 do begin if cbi,i0 then d:=min(d,cbi,i-fbi,i); 正向邊 if ci,bi0 then d:=min(d,fi,bi); 逆向邊 i:=bi; end; i:=n; while bi0 do 逆向更新每條邊的流量 begin if cbi,i0 then in

10、c(fbi,i,d); 正向邊 if ci,bi0 then dec(fi,bi,d); 逆向邊 i:=bi; end; inc(sum,d); 總流量增加d24主程序：主程序： for i:=1 to n do bi:= -1; 初始化增廣路徑 b1:=0; while findflow(1) do 增廣流 begin addflow; for i:=1 to n do bi:=-1; b1:=0; end; writeln(sum); 輸出最大流 for i:=1 to n do 輸出每條邊的流量 for j:=1 to n do if fi,j0 then writeln(i,-,j,

11、,fi,j);25優(yōu)化 殘留網(wǎng)絡(luò) d 的設(shè)置： 若存在 ( u, v ) 則 d ( u, v ) = c ( u, v ) f ( u, v ) d ( v, u ) = f ( u, v ) d ( u, v ) 是 從 u 到 v 能增加的最大流量理解: (u,v) 的流量為f(u,v),作為正向邊還可以增加的量是c ( u, v ) f ( u, v )，作為逆向邊，還可以增加的流量為： f ( u, v )。增廣路上正向邊流量增加，逆向邊增加流量減少。1243564234522212435642345222 d ( u, v ) = c ( u, v ) d ( v, u ) = 0

12、26深搜找增廣路徑過程function find( k:integer ):boolean; if k=n then exit(true); for i:=1 to n do if (bi= -1) and (dk,i0) then bi:=k; if find(i) then exit(true); / 此處bi不需要變回-1 exit(false);/ b1=0; b2 n= -1; 主函數(shù)中調(diào)用find(1)27廣搜找增廣路徑過程function bfsbfs:boolean; a 是廣搜隊(duì)列 for i:=1 to n do bi:=-1; b 是前驅(qū) b1:=0; a1:=1; op

13、en:=0; closed:=1; while open0) then inc(closed); aclosed:=i; bi:=k; if i=n then exit(true); 找到增廣路 exit(false); 沒找到增廣路28 增廣過程 min:=maxint; i:=n; while bi0 (i1) do /逆向求增加流min if mindbi,i then min:=dbi,i; i:=bi; i:=n; while bi0 (i1) do/ /逆向修改流量 dec(dbi,i,min); inc(di,bi,min); i:=bi; inc(sum,min); sum是總

14、流量29問題1：奶牛的新年晚會 奶牛們要舉辦一次別開生面的新年晚會。每頭奶牛會做奶牛們要舉辦一次別開生面的新年晚會。每頭奶牛會做一些不同樣式的食品（單位是盤）。到時(shí)候他們會把自己最一些不同樣式的食品（單位是盤）。到時(shí)候他們會把自己最拿手的不超過拿手的不超過k k樣食品各做一盤帶到晚會，和其他奶牛一起樣食品各做一盤帶到晚會，和其他奶牛一起分享。但考慮到食品太多會浪費(fèi)掉，他們給每種食品的總盤分享。但考慮到食品太多會浪費(fèi)掉，他們給每種食品的總盤數(shù)都規(guī)定了一個不一定相同的上限值。這讓他們很傷腦筋，數(shù)都規(guī)定了一個不一定相同的上限值。這讓他們很傷腦筋，究竟應(yīng)該怎樣做，才能讓晚會上食品的總盤數(shù)盡量的多呢？究

15、竟應(yīng)該怎樣做，才能讓晚會上食品的總盤數(shù)盡量的多呢？ 例如：有例如：有4 4頭奶牛，每頭奶牛最多可以帶頭奶牛，每頭奶牛最多可以帶3 3盤食品。一盤食品。一共有共有5 5種食品，它們的數(shù)量上限是種食品，它們的數(shù)量上限是2 2、2 2、2 2、2 2、3 3。奶牛。奶牛1 1會會做食品做食品1414，奶牛，奶牛2 2會做食品會做食品2525，奶牛，奶牛3 3會做食品會做食品1 1、2 2、4 4，奶牛奶牛4 4會做食品會做食品1313。那么最多可以帶。那么最多可以帶9 9盤食品到晚會上。盤食品到晚會上。即奶牛即奶牛1 1做食品做食品2424，奶牛，奶牛2 2做食品做食品3535，奶奶，奶奶3 3做食品做食品1 1、2 2，奶牛奶牛4 4做食品做食品1 1。這樣，。這樣，4 4種食品各有種食品各有2 2、2