網(wǎng)絡(luò)流算法介紹課件

網(wǎng)絡(luò)算法介紹PPT網(wǎng)絡(luò)算法介紹PPT網(wǎng)絡(luò)流算法介紹1.基本概念2.最大流問(wèn)題求解3.二分圖匹配4.二分圖最佳匹配關(guān)鍵詞：源點(diǎn)、匯點(diǎn)、容量、流量、殘量、費(fèi)用、增廣路徑網(wǎng)絡(luò)流算法介紹1.基本概念關(guān)鍵詞：源點(diǎn)、匯點(diǎn)、容量、網(wǎng)絡(luò)流問(wèn)題類比：求最短路徑 把實(shí)際問(wèn)題的道路地圖抽象為有向圖，然后用一定算法求解最短路徑。 我們也可以將一個(gè)有向圖看作一個(gè)流網(wǎng)絡(luò)來(lái)解決另一類型的問(wèn)題。 匹配問(wèn)題、運(yùn)輸問(wèn)題、任務(wù)分配問(wèn)題。。。網(wǎng)絡(luò)流問(wèn)題類比：求最短路徑流網(wǎng)絡(luò)定義（FlowNetwork）V表示整個(gè)圖中的所有結(jié)點(diǎn)的集合.E表示整個(gè)圖中所有邊的集合.G=(V,E),表示整個(gè)有向圖.s表示網(wǎng)絡(luò)的源點(diǎn),t表示網(wǎng)絡(luò)的匯點(diǎn).對(duì)于每條邊(u,v),有一個(gè)容量c(u,v)(c(u,v)>=0)如果c(u,v)=0，則表示(u,v)不在網(wǎng)絡(luò)中。如果原網(wǎng)絡(luò)中不存在邊(u,v)，則令c(u,v)=0對(duì)于每條邊(u,v),有一個(gè)流量f(u,v).流網(wǎng)絡(luò)定義（FlowNetwork）V表示整個(gè)圖中的所有結(jié)流網(wǎng)絡(luò)示例水源源點(diǎn)S蓄水池匯點(diǎn)T水管/邊流速限制容量c流速/流量f流網(wǎng)絡(luò)示例水源蓄水池水管/邊流速限制容量c流速/流量f網(wǎng)絡(luò)流三個(gè)性質(zhì)容量限制：f(u,v)<=c(u,v)對(duì)稱性：f(u,v)==-f(v,u)收支平衡:對(duì)于不是源點(diǎn)也不是匯點(diǎn)的任意結(jié)點(diǎn),流入該結(jié)點(diǎn)的流量和等于流出該結(jié)點(diǎn)的流量和。只要滿足這三個(gè)性質(zhì),就是一個(gè)合法的網(wǎng)絡(luò)流.網(wǎng)絡(luò)流三個(gè)性質(zhì)容量限制：f(u,v)<=c(u,v)網(wǎng)絡(luò)的流量、最大流一個(gè)合法的網(wǎng)絡(luò)流量|f|定義為：從源點(diǎn)流出的流量 ∑f(s,v)流向匯點(diǎn)的流量 ∑f(v,t)|f|的最大值表示為最大流網(wǎng)絡(luò)的流量、最大流一個(gè)合法的網(wǎng)絡(luò)流量|f|定義為：流網(wǎng)絡(luò)示例收支平衡容量限制f(v4,v6)=-f(v6,v4)=1f(v6,v4)圖中不給出網(wǎng)絡(luò)的流量|f|=5+3=8或等于5+2+1(匯點(diǎn)處)0<=|f|<=最大流流網(wǎng)絡(luò)示例收支平衡容量限制f(v4,v6)=-f(v6,殘量網(wǎng)絡(luò)對(duì)于網(wǎng)絡(luò)中的每一條邊，計(jì)算容量與流量的差即表示為殘量。R(u,v)=C(u,v)–F(u,v)形象的說(shuō)，一條邊的殘量即為該邊還能流過(guò)的流量。殘量網(wǎng)絡(luò)對(duì)于網(wǎng)絡(luò)中的每一條邊，計(jì)算容量與流量的差即表示為殘量殘量網(wǎng)絡(luò)舉例v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原網(wǎng)絡(luò)殘量網(wǎng)絡(luò)殘量網(wǎng)絡(luò)舉例v1tsv2(2,2)(4,4)(2,4)(0,殘量網(wǎng)絡(luò)從殘量網(wǎng)絡(luò)中可以清楚地看到：因?yàn)榇嬖谶?s,v2)=3,則知道從S到v2還可以再增加2單位的流量；因?yàn)榇嬖谶?v1,t)=2,則從v1到t還可以再增加2單位的流量。v1tsv2232422殘量網(wǎng)絡(luò)從殘量網(wǎng)絡(luò)中可以清楚地看到：v1tsv2232422后向弧其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s還可以增加4單位的流量。但是從v1到s和原網(wǎng)絡(luò)中的弧的方向相反。這樣的弧稱為后向弧。問(wèn)題：有必要建后向弧線？tsv232422v1后向弧其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s為什么要建立后向弧在尋找最大流的過(guò)程中，有些弧的選擇一開(kāi)始可能就是錯(cuò)誤的。所以在路徑中加上后向弧，作為標(biāo)記。當(dāng)發(fā)現(xiàn)了另一條可增廣的路徑是并包含后向弧，意味這條路徑對(duì)以前對(duì)這條弧頂選擇進(jìn)行取消后向弧為算法糾正自己所犯的錯(cuò)誤提供了可能性，它允許算法取消先前的錯(cuò)誤的行為為什么要建立后向弧在尋找最大流的過(guò)程中，有些弧的選擇一開(kāi)始可增廣路徑在殘量網(wǎng)絡(luò)中，從源點(diǎn)S出發(fā)到匯點(diǎn)T的一條路徑。增廣路徑上的最小殘量表示該網(wǎng)絡(luò)還可增加的額外流量。增廣路徑點(diǎn)集間的流量定義點(diǎn)集間的流量：f(X,Y)=∑∑f(x,y)則有：

f(X,X)=0 (流的對(duì)稱性) f(X,Y)=-f(Y,X) (流的對(duì)稱性) f(X∪Y,Z)=f(X,Z)+f(Y,Z) f(X,Y∪Z)=f(X,Y)+f(X,Z)x∈Xy∈Y點(diǎn)集間的流量定義點(diǎn)集間的流量：f(X,Y)=∑∑f(點(diǎn)集間的流量不包含s,t的點(diǎn)集，與它關(guān)聯(lián)的邊上的流量和為零證明：f(X,V)=∑{∑f(x,v)} =∑0 (流量收支平衡)

=0x∈Xv∈Vx∈X點(diǎn)集間的流量不包含s,t的點(diǎn)集，與它關(guān)聯(lián)的邊上的流量和為零x網(wǎng)絡(luò)中的割割（S,T）由兩個(gè)點(diǎn)集S,T組成，滿足

1、S+T=V 2、源點(diǎn)在S集合中

3、匯點(diǎn)在T集合中

4、f(S,T)表示割的流量

5、c(S,T)表示割的容量最小切割時(shí)使c(S,T)最小的切割網(wǎng)絡(luò)中的割割（S,T）由兩個(gè)點(diǎn)集S,T組成，滿足割的流量任意割的流量等于網(wǎng)絡(luò)的流量證明：

f(S,T)=f(S,V)–f(S,S) =f(S,V)+0=f(s,V)+f(S-{s},V)=f(s,V)+0=|f|割的流量任意割的流量等于網(wǎng)絡(luò)的流量割的流量網(wǎng)絡(luò)的流量小等于任意割的容量證明：

|f|=f(S,T)=∑∑f(x,y) <=∑∑c(x,y)=c(S,T)所以有最小割等于最大流x∈Sy∈Tx∈Sy∈T割的流量網(wǎng)絡(luò)的流量小等于任意割的容量x∈Sy∈Tx∈Sy∈T最小割最大流定理網(wǎng)絡(luò)的最大流等于最小割f是網(wǎng)絡(luò)的最大流殘量網(wǎng)絡(luò)中無(wú)可增廣路徑存在某個(gè)切割(S,T),使f=c(S,T)以上三個(gè)命題是等價(jià)的，證明之：最小割最大流定理網(wǎng)絡(luò)的最大流等于最小割1—>2反證法假設(shè)殘量網(wǎng)絡(luò)中還有增廣路徑，增廣路徑上的流量至少為1由該路徑增廣后的流量>f與f是最大流矛盾1—>2反證法2—>3此時(shí)的殘量網(wǎng)絡(luò)中不存在s-t通路定義S為s可達(dá)的點(diǎn)集定義T為可達(dá)t的點(diǎn)集顯然S＋T=V(S,T)中所有弧都滿載，否則殘量網(wǎng)絡(luò)將不為0，使s-t有通路所以|f|=c(S,T)2—>3此時(shí)的殘量網(wǎng)絡(luò)中不存在s-t通路3—>1由|f|<=c(S,T)（任意割）當(dāng)|f|==c(S,T)|f|為最大值 從上面的證明，我們可以得到求最大流從增廣路徑算法。 從2->3的證明給出了從最大流構(gòu)造最小割的過(guò)程，即求出s的可達(dá)點(diǎn)集S， 再令T=V-S3—>1由|f|<=c(S,T)（任意割）求最大流的增廣路算法每次用BFS找一條最短的增廣路徑；然后沿著這條路徑修改流量值（實(shí)際修改的是殘量網(wǎng)絡(luò)的邊權(quán)）。 路徑上的后向弧+流量值 路徑上的前向弧-流量值當(dāng)沒(méi)有增廣路時(shí)，算法停止，此時(shí)的流就是最大流。求最大流的增廣路算法每次用BFS找一條最短的增廣路徑；最大流例題BOJ1154典型的最大流問(wèn)題已知網(wǎng)絡(luò)容量,求最大流量根據(jù)題意構(gòu)圖如下: 1為源點(diǎn),M為匯點(diǎn).

容量為題目已知給出,可能的情況是相同兩個(gè)結(jié)點(diǎn)之間有多條水渠,將它們累加即可.

初始化流量網(wǎng)絡(luò)為0,則殘量網(wǎng)絡(luò)即初始為容量網(wǎng)絡(luò).算法流程:

構(gòu)圖->求最大流->輸出最大流最大流例題BOJ1154典型的最大流問(wèn)題最大流例題BOJ1154尋找增廣路boolfindload(){memset(visited,0,sizeof(visited));head=tail=0;queue[tail++]=s;while(head<tail){j=queue[head++];for(i=1;i<=m;i++)if(!visited[i]&&cap[j][i]>0)//cap為容量,本題可以直接表示為殘量

{pre[i]=j;//路徑標(biāo)志

visited[i]=1;if(i==t)returntrue;//找到s-t通路

queue[tail++]=i;}returnfalse;}

最大流例題BOJ1154尋找增廣路最大流例題BOJ1154求最大流intmaxflow(){inti,j,flow=0,min;//min為增廣路徑上的瓶頸流量;flow網(wǎng)絡(luò)最大流

while(findload()){min=0x7ffffff;for(i=t;i!=s;i=pre[i])min<?=cap[pre[i]][i];//找增廣路徑的瓶頸流量

flow+=min;for(i=t;i!=s;i=pre[i])//更新路徑上的流量

{cap[pre[i]][i]-=min;//前向弧加mincap[i][pre[i]]+=min;//后向弧減min}}returnflow;}最大流例題BOJ1154求最大流最大流模型構(gòu)圖對(duì)于求流網(wǎng)絡(luò)最大流的算法我們可以有現(xiàn)成的模板套用，在實(shí)際問(wèn)題中，如何去構(gòu)圖建立最大流模型才是解決問(wèn)題的難點(diǎn)和關(guān)鍵。構(gòu)圖一般考慮下面幾個(gè)要素: 1、問(wèn)題是否符合求源點(diǎn)到目標(biāo)點(diǎn)的所經(jīng)過(guò)網(wǎng)絡(luò)的等效最大流。

2、找準(zhǔn)源點(diǎn)和匯點(diǎn)

3、源點(diǎn)和網(wǎng)絡(luò)中的點(diǎn)，匯點(diǎn)和網(wǎng)絡(luò)中點(diǎn)的關(guān)系。

4、網(wǎng)絡(luò)中的個(gè)點(diǎn)的關(guān)系。

5、明確什么是容量、流量、殘量。最大流模型構(gòu)圖對(duì)于求流網(wǎng)絡(luò)最大流的算法我們可以有現(xiàn)成的模板套Leapin'Lizards題意:有一間房子,有n*m個(gè)pillars,第一個(gè)矩陣表示相應(yīng)的pillars能跳幾個(gè)Lizards,第二個(gè)矩陣表示哪個(gè)pillars上有Lizard.d表示能跳的最大范圍.Lizard跳出邊界就能逃跑,問(wèn)最少還有幾個(gè)Lizards跑不了.思路:拆點(diǎn),最大流.將每個(gè)>0的pillars拆開(kāi),有L的點(diǎn)由源點(diǎn)向其引一條邊,邊容量為1,能跳出邊界的點(diǎn)向匯點(diǎn)引邊,邊容量為無(wú)窮.其他題目:pku3498Leapin'Lizards題意:有一間房子,有n*m個(gè)CableTVNetwork題意:一個(gè)無(wú)向圖,問(wèn)去掉幾個(gè)點(diǎn)使得其不連通.思路:最小點(diǎn)割集,根據(jù)最小割最大流定理求解.拆點(diǎn),求最大流.因?yàn)榇祟}沒(méi)有明確的源點(diǎn)和匯點(diǎn),所以要枚舉源點(diǎn)和匯點(diǎn),然后求最大流,最大流的最小值就是最小割的最小值.其他題目：POJ3469CableTVNetwork題意:一個(gè)無(wú)向圖,問(wèn)去掉幾二分圖二分圖作為流網(wǎng)絡(luò)的一個(gè)特例，我們既可以特別去討論它，也可以從網(wǎng)絡(luò)流的角度來(lái)理解它。定義：二分圖又稱二部圖，它是一個(gè)無(wú)向圖，圖的頂點(diǎn)分成兩個(gè)不相交的點(diǎn)集X,Y.

對(duì)于圖中任意一條邊的兩端點(diǎn)分別來(lái)自不同點(diǎn)集。112233445二分圖二分圖作為流網(wǎng)絡(luò)的一個(gè)特例，我們既可以特別去討論它，也二分圖匹配給定二分圖G，在G的子圖M中，M的任意兩條邊都不共點(diǎn)，則稱M為G圖的一個(gè)匹配。M中邊數(shù)最大的子集稱為G的最大匹配。如果在最大匹配中，邊涵蓋了圖中所有的點(diǎn)，則這樣的匹配為完美匹配。二分圖匹配給定二分圖G，在G的子圖M中，M的任意兩條邊都不共匈牙利算法實(shí)際上它也是一種不斷尋找增廣路徑的算法增廣路徑定義： 若path是圖G中一條連通兩個(gè)未匹配頂點(diǎn)(分別屬于X,Y)的路徑， 并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在Path上交替出現(xiàn)， 則稱Path為相對(duì)于M的一條增廣路徑。匈牙利算法實(shí)際上它也是一種不斷尋找增廣路徑的算法二分圖增廣路由增廣路定義可以得出：

1、path的長(zhǎng)度必為奇數(shù)，且第一條邊和最后一條邊為不匹配邊。

2、path經(jīng)過(guò)路徑取反操作以后，得到比當(dāng)前更大的匹配。

3、當(dāng)找不到增廣路徑時(shí)候，得到的匹配即為最大匹配。與增廣路求最大流算法很類似二分圖增廣路由增廣路定義可以得出：最大流和二分圖匹配實(shí)際上二分圖可以改造成一個(gè)流網(wǎng)絡(luò)把X，Y的邊改成從X到Y(jié)的有向邊，并賦值為1，表示從X到Y(jié)容量為1。添加源點(diǎn)s，s到X部每個(gè)點(diǎn)的容量都為1。添加匯點(diǎn)t，Y到t部每個(gè)點(diǎn)的容量都為1。以此建立的流網(wǎng)絡(luò)求得到最大流，即為原二分圖中的最大匹配數(shù)。最大流和二分圖匹配實(shí)際上二分圖可以改造成一個(gè)流網(wǎng)絡(luò)最大流和二分圖匹配對(duì)上述的流網(wǎng)絡(luò)求最大流的增廣路算法我們已經(jīng)了解了。每次找增廣路時(shí)必然是以條從s到t的通路，除去s到X,Y到t兩條邊，剩下的邊必然是在原二分圖中交替前進(jìn)。前向弧表示尚未匹配的邊后向弧表示已經(jīng)匹配的邊路徑取反操作實(shí)際上是更新流量操作最大流和二分圖匹配對(duì)上述的流網(wǎng)絡(luò)求最大流的增廣路算法我們已經(jīng)二分圖匹配的構(gòu)圖首先劃分“對(duì)立”的兩個(gè)集合明確每個(gè)匹配關(guān)系的含義明確最大匹配的意義從最大流的構(gòu)圖方法來(lái)入手二分圖匹配的構(gòu)圖首先劃分“對(duì)立”的兩個(gè)集合二分圖匹配例題BOJ1155中文題目,題意好理解構(gòu)圖:考慮將墻面看成一個(gè)國(guó)際象棋的棋盤,那么每塊瓷磚貼在棋盤上必然占一格白格和一格黑格.用棋盤的黑色格子表示二分圖X部用棋盤的黑色格子表示二分圖Y部相鄰的格子用一條邊連接二分圖匹配例題BOJ1155中文題目,題意好理解二分圖匹配例題BOJ1155找增廣路徑intpath(intv)//從X部的V點(diǎn)找增廣路徑{ for(inti=1;i<=m;i++) { if(g[v][i]&&!visited[i])//找到未匹配邊

{ visited[i]=true; if(match[i]==-1||path(match[i])==1) { match[i]=v;//路徑取反操作

return1; } } } return0;}二分圖匹配例題BOJ1155找增廣路徑二分圖匹配例題BOJ1155求最大匹配

cnt=0;//最大匹配數(shù)

memset(match,-1,sizeof(match));for(i=1;i<=n;i++){memset(visited,0,sizeof(visited));cnt+=path(i);}二分圖匹配例題BOJ1155求最大匹配Asteroids題意：有一種超級(jí)武器，能摧毀一行或一列上的物體，現(xiàn)在有n*n的圖，k個(gè)物體，最少多少次摧毀。思路：覆蓋問(wèn)題，用最少的線覆蓋所有的點(diǎn)，二分圖匹配，以點(diǎn)為邊，以行和列為點(diǎn)，有物體的點(diǎn)的行和列連邊，進(jìn)行二分圖最大匹配。其他題目：pku146920602226Asteroids題意：有一種超級(jí)武器，能摧毀一行或一列上AirRaid題意：有n個(gè)點(diǎn)，k條有向邊，無(wú)環(huán)。求最少幾次將整個(gè)圖遍歷完，每個(gè)點(diǎn)只能走一次。思路：最小路徑覆蓋=n-最大匹配，構(gòu)造二分圖，求最大匹配。入點(diǎn)，出點(diǎn)構(gòu)成二分圖，若i，j之間有邊，則i的出點(diǎn)向j的入點(diǎn)連邊，每匹配一對(duì)點(diǎn)，說(shuō)明該路徑能覆蓋兩個(gè)點(diǎn)，所以最小路徑覆蓋數(shù)減一。相關(guān)：pku2594AirRaid題意：有n個(gè)點(diǎn)，k條有向邊，無(wú)環(huán)。求最少幾二分圖最佳匹配在二分圖中的每條邊都帶上一個(gè)權(quán)值，求權(quán)和最大的匹配就叫二分圖最佳匹配。具體模型BOJ上1080，1084就是非常赤裸的最佳匹配模型。求二分圖最佳匹配的算法。二分圖最佳匹配在二分圖中的每條邊都帶上一個(gè)權(quán)值，求權(quán)和最大的KM算法給出每個(gè)頂點(diǎn)可行頂標(biāo)lx,ly，對(duì)于所有邊e(i,j)都有l(wèi)x[i]+ly[j]>=w[i][j];對(duì)于所有邊e(i,j)在M中，都有

lx[i]+ly[j]==w[i][j];則M是G的最佳匹配KM算法給出每個(gè)頂點(diǎn)可行頂標(biāo)lx,ly，對(duì)于所有邊e(i,二分圖最佳匹配先將一個(gè)未被匹配的頂點(diǎn)u做一次增廣路，記下哪些結(jié)點(diǎn)被訪問(wèn)那些結(jié)點(diǎn)沒(méi)有被訪問(wèn)。求出d=min{lx[i]+ly[j]-w[i,j]}其中i結(jié)點(diǎn)被訪問(wèn)，j結(jié)點(diǎn)沒(méi)有被訪問(wèn)。調(diào)整lx和ly：對(duì)于訪問(wèn)過(guò)的x頂點(diǎn)，將它的可行標(biāo)減去d，訪問(wèn)過(guò)的y頂點(diǎn)，將它的可行標(biāo)增加d。修改后的頂標(biāo)仍是可行頂標(biāo)，原來(lái)的匹配M仍然存在，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。二分圖最佳匹配先將一個(gè)未被匹配的頂點(diǎn)u做一次增廣路，記下哪些算法流程(1)初始化可行頂標(biāo)的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標(biāo)的值(4)重復(fù)(2)(3)直到找到相等子圖的完備匹配為止算法流程(1)初始化可行頂標(biāo)的值二分圖最佳匹配例題BOJ1080題目意思非常清晰構(gòu)圖非常明確,工作為X,人為YX到Y(jié)的權(quán)值已知求X到Y(jié)的最小匹配把X到Y(jié)的勸值改為負(fù)數(shù),求最佳匹配后,再取負(fù)數(shù),得到的就是最小匹配值.二分圖最佳匹配例題BOJ1080題目意思非常清晰二分圖最佳匹配例題BOJ1080找增廣路徑intfind(intv){inti,tmp;x[v]=1;for(i=0;i<n;i++)if(!y[i]&&lx[v]+ly[i]==map[v][i]){tmp=match[i];match[i]=v;y[i]=1;if(tmp==-1||find(tmp))return1;match[i]=tmp;}return0;}二分圖最佳匹配例題BOJ1080找增廣路徑二分圖最佳匹配例題BOJ1080intKM(){inti,j,k,d,ans;for(k=0;k<n;k++)while(1){memset(x,0,sizeof(x));memset(y,0,sizeof(y));if(find(k))break;//找完美匹配子圖

for(d=MAX,i=0;i<n;i++)if(x[i])for(j=0;j<n;j++)if(!y[j])d<?=lx[i]+ly[j]-map[i][j];for(i=0;i<n;i++){if(x[i])lx[i]-=d;if(y[i])ly[i]+=d;}}for(ans=0,i=0;i<n;i++)ans+=map[match[i]][i];returnans;}/*可行頂標(biāo)ly記為0，lx記為與x相連的邊的權(quán)最大值*/memset(ly,0,sizeof(ly));memset(match,-1,sizeof(match));for(i=0;i<n;i++){lx[i]=-MAX;for(j=0;j<n;j++)lx[i]>?=map[i][j];}二分圖最佳匹配例題BOJ1080intKM()/*可行頂總結(jié)網(wǎng)絡(luò)流模型可以用來(lái)解決很多關(guān)于分配求最優(yōu)值得問(wèn)題，它的最大流，最小費(fèi)用最大流求解算法我們已經(jīng)大概了解。在更多的實(shí)際問(wèn)題中，網(wǎng)絡(luò)流模型的建立往往是難點(diǎn)。巧妙的建立一個(gè)模型往往能誕生一個(gè)優(yōu)質(zhì)的算法?？偨Y(jié)網(wǎng)絡(luò)流模型可以用來(lái)解決很多關(guān)于分配求最優(yōu)值得問(wèn)題，它的最Thankyou!網(wǎng)絡(luò)流算法介紹課件網(wǎng)絡(luò)算法介紹PPT網(wǎng)絡(luò)算法介紹PPT網(wǎng)絡(luò)流算法介紹1.基本概念2.最大流問(wèn)題求解3.二分圖匹配4.二分圖最佳匹配關(guān)鍵詞：源點(diǎn)、匯點(diǎn)、容量、流量、殘量、費(fèi)用、增廣路徑網(wǎng)絡(luò)流算法介紹1.基本概念關(guān)鍵詞：源點(diǎn)、匯點(diǎn)、容量、網(wǎng)絡(luò)流問(wèn)題類比：求最短路徑 把實(shí)際問(wèn)題的道路地圖抽象為有向圖，然后用一定算法求解最短路徑。 我們也可以將一個(gè)有向圖看作一個(gè)流網(wǎng)絡(luò)來(lái)解決另一類型的問(wèn)題。 匹配問(wèn)題、運(yùn)輸問(wèn)題、任務(wù)分配問(wèn)題。。。網(wǎng)絡(luò)流問(wèn)題類比：求最短路徑流網(wǎng)絡(luò)定義（FlowNetwork）V表示整個(gè)圖中的所有結(jié)點(diǎn)的集合.E表示整個(gè)圖中所有邊的集合.G=(V,E),表示整個(gè)有向圖.s表示網(wǎng)絡(luò)的源點(diǎn),t表示網(wǎng)絡(luò)的匯點(diǎn).對(duì)于每條邊(u,v),有一個(gè)容量c(u,v)(c(u,v)>=0)如果c(u,v)=0，則表示(u,v)不在網(wǎng)絡(luò)中。如果原網(wǎng)絡(luò)中不存在邊(u,v)，則令c(u,v)=0對(duì)于每條邊(u,v),有一個(gè)流量f(u,v).流網(wǎng)絡(luò)定義（FlowNetwork）V表示整個(gè)圖中的所有結(jié)流網(wǎng)絡(luò)示例水源源點(diǎn)S蓄水池匯點(diǎn)T水管/邊流速限制容量c流速/流量f流網(wǎng)絡(luò)示例水源蓄水池水管/邊流速限制容量c流速/流量f網(wǎng)絡(luò)流三個(gè)性質(zhì)容量限制：f(u,v)<=c(u,v)對(duì)稱性：f(u,v)==-f(v,u)收支平衡:對(duì)于不是源點(diǎn)也不是匯點(diǎn)的任意結(jié)點(diǎn),流入該結(jié)點(diǎn)的流量和等于流出該結(jié)點(diǎn)的流量和。只要滿足這三個(gè)性質(zhì),就是一個(gè)合法的網(wǎng)絡(luò)流.網(wǎng)絡(luò)流三個(gè)性質(zhì)容量限制：f(u,v)<=c(u,v)網(wǎng)絡(luò)的流量、最大流一個(gè)合法的網(wǎng)絡(luò)流量|f|定義為：從源點(diǎn)流出的流量 ∑f(s,v)流向匯點(diǎn)的流量 ∑f(v,t)|f|的最大值表示為最大流網(wǎng)絡(luò)的流量、最大流一個(gè)合法的網(wǎng)絡(luò)流量|f|定義為：流網(wǎng)絡(luò)示例收支平衡容量限制f(v4,v6)=-f(v6,v4)=1f(v6,v4)圖中不給出網(wǎng)絡(luò)的流量|f|=5+3=8或等于5+2+1(匯點(diǎn)處)0<=|f|<=最大流流網(wǎng)絡(luò)示例收支平衡容量限制f(v4,v6)=-f(v6,殘量網(wǎng)絡(luò)對(duì)于網(wǎng)絡(luò)中的每一條邊，計(jì)算容量與流量的差即表示為殘量。R(u,v)=C(u,v)–F(u,v)形象的說(shuō)，一條邊的殘量即為該邊還能流過(guò)的流量。殘量網(wǎng)絡(luò)對(duì)于網(wǎng)絡(luò)中的每一條邊，計(jì)算容量與流量的差即表示為殘量殘量網(wǎng)絡(luò)舉例v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原網(wǎng)絡(luò)殘量網(wǎng)絡(luò)殘量網(wǎng)絡(luò)舉例v1tsv2(2,2)(4,4)(2,4)(0,殘量網(wǎng)絡(luò)從殘量網(wǎng)絡(luò)中可以清楚地看到：因?yàn)榇嬖谶?s,v2)=3,則知道從S到v2還可以再增加2單位的流量；因?yàn)榇嬖谶?v1,t)=2,則從v1到t還可以再增加2單位的流量。v1tsv2232422殘量網(wǎng)絡(luò)從殘量網(wǎng)絡(luò)中可以清楚地看到：v1tsv2232422后向弧其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s還可以增加4單位的流量。但是從v1到s和原網(wǎng)絡(luò)中的弧的方向相反。這樣的弧稱為后向弧。問(wèn)題：有必要建后向弧線？tsv232422v1后向弧其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s為什么要建立后向弧在尋找最大流的過(guò)程中，有些弧的選擇一開(kāi)始可能就是錯(cuò)誤的。所以在路徑中加上后向弧，作為標(biāo)記。當(dāng)發(fā)現(xiàn)了另一條可增廣的路徑是并包含后向弧，意味這條路徑對(duì)以前對(duì)這條弧頂選擇進(jìn)行取消后向弧為算法糾正自己所犯的錯(cuò)誤提供了可能性，它允許算法取消先前的錯(cuò)誤的行為為什么要建立后向弧在尋找最大流的過(guò)程中，有些弧的選擇一開(kāi)始可增廣路徑在殘量網(wǎng)絡(luò)中，從源點(diǎn)S出發(fā)到匯點(diǎn)T的一條路徑。增廣路徑上的最小殘量表示該網(wǎng)絡(luò)還可增加的額外流量。增廣路徑點(diǎn)集間的流量定義點(diǎn)集間的流量：f(X,Y)=∑∑f(x,y)則有：

f(X,X)=0 (流的對(duì)稱性) f(X,Y)=-f(Y,X) (流的對(duì)稱性) f(X∪Y,Z)=f(X,Z)+f(Y,Z) f(X,Y∪Z)=f(X,Y)+f(X,Z)x∈Xy∈Y點(diǎn)集間的流量定義點(diǎn)集間的流量：f(X,Y)=∑∑f(點(diǎn)集間的流量不包含s,t的點(diǎn)集，與它關(guān)聯(lián)的邊上的流量和為零證明：f(X,V)=∑{∑f(x,v)} =∑0 (流量收支平衡)

=0x∈Xv∈Vx∈X點(diǎn)集間的流量不包含s,t的點(diǎn)集，與它關(guān)聯(lián)的邊上的流量和為零x網(wǎng)絡(luò)中的割割（S,T）由兩個(gè)點(diǎn)集S,T組成，滿足

1、S+T=V 2、源點(diǎn)在S集合中

3、匯點(diǎn)在T集合中

4、f(S,T)表示割的流量

5、c(S,T)表示割的容量最小切割時(shí)使c(S,T)最小的切割網(wǎng)絡(luò)中的割割（S,T）由兩個(gè)點(diǎn)集S,T組成，滿足割的流量任意割的流量等于網(wǎng)絡(luò)的流量證明：

f(S,T)=f(S,V)–f(S,S) =f(S,V)+0=f(s,V)+f(S-{s},V)=f(s,V)+0=|f|割的流量任意割的流量等于網(wǎng)絡(luò)的流量割的流量網(wǎng)絡(luò)的流量小等于任意割的容量證明：

|f|=f(S,T)=∑∑f(x,y) <=∑∑c(x,y)=c(S,T)所以有最小割等于最大流x∈Sy∈Tx∈Sy∈T割的流量網(wǎng)絡(luò)的流量小等于任意割的容量x∈Sy∈Tx∈Sy∈T最小割最大流定理網(wǎng)絡(luò)的最大流等于最小割f是網(wǎng)絡(luò)的最大流殘量網(wǎng)絡(luò)中無(wú)可增廣路徑存在某個(gè)切割(S,T),使f=c(S,T)以上三個(gè)命題是等價(jià)的，證明之：最小割最大流定理網(wǎng)絡(luò)的最大流等于最小割1—>2反證法假設(shè)殘量網(wǎng)絡(luò)中還有增廣路徑，增廣路徑上的流量至少為1由該路徑增廣后的流量>f與f是最大流矛盾1—>2反證法2—>3此時(shí)的殘量網(wǎng)絡(luò)中不存在s-t通路定義S為s可達(dá)的點(diǎn)集定義T為可達(dá)t的點(diǎn)集顯然S＋T=V(S,T)中所有弧都滿載，否則殘量網(wǎng)絡(luò)將不為0，使s-t有通路所以|f|=c(S,T)2—>3此時(shí)的殘量網(wǎng)絡(luò)中不存在s-t通路3—>1由|f|<=c(S,T)（任意割）當(dāng)|f|==c(S,T)|f|為最大值 從上面的證明，我們可以得到求最大流從增廣路徑算法。 從2->3的證明給出了從最大流構(gòu)造最小割的過(guò)程，即求出s的可達(dá)點(diǎn)集S， 再令T=V-S3—>1由|f|<=c(S,T)（任意割）求最大流的增廣路算法每次用BFS找一條最短的增廣路徑；然后沿著這條路徑修改流量值（實(shí)際修改的是殘量網(wǎng)絡(luò)的邊權(quán)）。 路徑上的后向弧+流量值 路徑上的前向弧-流量值當(dāng)沒(méi)有增廣路時(shí)，算法停止，此時(shí)的流就是最大流。求最大流的增廣路算法每次用BFS找一條最短的增廣路徑；最大流例題BOJ1154典型的最大流問(wèn)題已知網(wǎng)絡(luò)容量,求最大流量根據(jù)題意構(gòu)圖如下: 1為源點(diǎn),M為匯點(diǎn).

容量為題目已知給出,可能的情況是相同兩個(gè)結(jié)點(diǎn)之間有多條水渠,將它們累加即可.

初始化流量網(wǎng)絡(luò)為0,則殘量網(wǎng)絡(luò)即初始為容量網(wǎng)絡(luò).算法流程:

構(gòu)圖->求最大流->輸出最大流最大流例題BOJ1154典型的最大流問(wèn)題最大流例題BOJ1154尋找增廣路boolfindload(){memset(visited,0,sizeof(visited));head=tail=0;queue[tail++]=s;while(head<tail){j=queue[head++];for(i=1;i<=m;i++)if(!visited[i]&&cap[j][i]>0)//cap為容量,本題可以直接表示為殘量

{pre[i]=j;//路徑標(biāo)志

visited[i]=1;if(i==t)returntrue;//找到s-t通路

queue[tail++]=i;}returnfalse;}

最大流例題BOJ1154尋找增廣路最大流例題BOJ1154求最大流intmaxflow(){inti,j,flow=0,min;//min為增廣路徑上的瓶頸流量;flow網(wǎng)絡(luò)最大流

while(findload()){min=0x7ffffff;for(i=t;i!=s;i=pre[i])min<?=cap[pre[i]][i];//找增廣路徑的瓶頸流量

flow+=min;for(i=t;i!=s;i=pre[i])//更新路徑上的流量

{cap[pre[i]][i]-=min;//前向弧加mincap[i][pre[i]]+=min;//后向弧減min}}returnflow;}最大流例題BOJ1154求最大流最大流模型構(gòu)圖對(duì)于求流網(wǎng)絡(luò)最大流的算法我們可以有現(xiàn)成的模板套用，在實(shí)際問(wèn)題中，如何去構(gòu)圖建立最大流模型才是解決問(wèn)題的難點(diǎn)和關(guān)鍵。構(gòu)圖一般考慮下面幾個(gè)要素: 1、問(wèn)題是否符合求源點(diǎn)到目標(biāo)點(diǎn)的所經(jīng)過(guò)網(wǎng)絡(luò)的等效最大流。

2、找準(zhǔn)源點(diǎn)和匯點(diǎn)

3、源點(diǎn)和網(wǎng)絡(luò)中的點(diǎn)，匯點(diǎn)和網(wǎng)絡(luò)中點(diǎn)的關(guān)系。

4、網(wǎng)絡(luò)中的個(gè)點(diǎn)的關(guān)系。

5、明確什么是容量、流量、殘量。最大流模型構(gòu)圖對(duì)于求流網(wǎng)絡(luò)最大流的算法我們可以有現(xiàn)成的模板套Leapin'Lizards題意:有一間房子,有n*m個(gè)pillars,第一個(gè)矩陣表示相應(yīng)的pillars能跳幾個(gè)Lizards,第二個(gè)矩陣表示哪個(gè)pillars上有Lizard.d表示能跳的最大范圍.Lizard跳出邊界就能逃跑,問(wèn)最少還有幾個(gè)Lizards跑不了.思路:拆點(diǎn),最大流.將每個(gè)>0的pillars拆開(kāi),有L的點(diǎn)由源點(diǎn)向其引一條邊,邊容量為1,能跳出邊界的點(diǎn)向匯點(diǎn)引邊,邊容量為無(wú)窮.其他題目:pku3498Leapin'Lizards題意:有一間房子,有n*m個(gè)CableTVNetwork題意:一個(gè)無(wú)向圖,問(wèn)去掉幾個(gè)點(diǎn)使得其不連通.思路:最小點(diǎn)割集,根據(jù)最小割最大流定理求解.拆點(diǎn),求最大流.因?yàn)榇祟}沒(méi)有明確的源點(diǎn)和匯點(diǎn),所以要枚舉源點(diǎn)和匯點(diǎn),然后求最大流,最大流的最小值就是最小割的最小值.其他題目：POJ3469CableTVNetwork題意:一個(gè)無(wú)向圖,問(wèn)去掉幾二分圖二分圖作為流網(wǎng)絡(luò)的一個(gè)特例，我們既可以特別去討論它，也可以從網(wǎng)絡(luò)流的角度來(lái)理解它。定義：二分圖又稱二部圖，它是一個(gè)無(wú)向圖，圖的頂點(diǎn)分成兩個(gè)不相交的點(diǎn)集X,Y.

對(duì)于圖中任意一條邊的兩端點(diǎn)分別來(lái)自不同點(diǎn)集。112233445二分圖二分圖作為流網(wǎng)絡(luò)的一個(gè)特例，我們既可以特別去討論它，也二分圖匹配給定二分圖G，在G的子圖M中，M的任意兩條邊都不共點(diǎn)，則稱M為G圖的一個(gè)匹配。M中邊數(shù)最大的子集稱為G的最大匹配。如果在最大匹配中，邊涵蓋了圖中所有的點(diǎn)，則這樣的匹配為完美匹配。二分圖匹配給定二分圖G，在G的子圖M中，M的任意兩條邊都不共匈牙利算法實(shí)際上它也是一種不斷尋找增廣路徑的算法增廣路徑定義： 若path是圖G中一條連通兩個(gè)未匹配頂點(diǎn)(分別屬于X,Y)的路徑， 并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在Path上交替出現(xiàn)， 則稱Path為相對(duì)于M的一條增廣路徑。匈牙利算法實(shí)際上它也是一種不斷尋找增廣路徑的算法二分圖增廣路由增廣路定義可以得出：

1、path的長(zhǎng)度必為奇數(shù)，且第一條邊和最后一條邊為不匹配邊。

2、path經(jīng)過(guò)路徑取反操作以后，得到比當(dāng)前更大的匹配。

3、當(dāng)找不到增廣路徑時(shí)候，得到的匹配即為最大匹配。與增廣路求最大流算法很類似二分圖增廣路由增廣路定義可以得出：最大流和二分圖匹配實(shí)際上二分圖可以改造成一個(gè)流網(wǎng)絡(luò)把X，Y的邊改成從X到Y(jié)的有向邊，并賦值為1，表示從X到Y(jié)容量為1。添加源點(diǎn)s，s到X部每個(gè)點(diǎn)的容量都為1。添加匯點(diǎn)t，Y到t部每個(gè)點(diǎn)的容量都為1。以此建立的流網(wǎng)絡(luò)求得到最大流，即為原二分圖中的最大匹配數(shù)。最大流和二分圖匹配實(shí)際上二分圖可以改造成一個(gè)流網(wǎng)絡(luò)最大流和二分圖匹配對(duì)上述的流網(wǎng)絡(luò)求最大流的增廣路算法我們已經(jīng)了解了。每次找增廣路時(shí)必然是以條從s到t的通路，除去s到X,Y到t兩條邊，剩下的邊必然是在原二分圖中交替前進(jìn)。前向弧表示尚未匹配的邊后向弧表示已經(jīng)匹配的邊路徑取反操作實(shí)際上是更新流量操作最大流和二分圖匹配對(duì)上述的流網(wǎng)絡(luò)求最大流的增廣路算法我們已經(jīng)二分圖匹配的構(gòu)圖首先劃分“對(duì)立”的兩個(gè)集合明確每個(gè)匹配關(guān)系的含義明確最大匹配的意義從最大流的構(gòu)圖方法來(lái)入手二分圖匹配的構(gòu)圖首先劃分“對(duì)立”的兩個(gè)集合二分圖匹配例題BOJ1155中文題目,題意好理解構(gòu)圖:考慮將墻面看成一個(gè)國(guó)際象棋的棋盤,那么每塊瓷磚貼在棋盤上必然占一格白格和一格黑格.用棋盤的黑色格子表示二分圖X部用棋盤的黑色格子表示二分圖Y部相鄰的格子用一條邊連接二分圖匹配例題BOJ1155中文題目,題意好理解二分圖匹配例題BOJ1155找增廣路徑intpath(intv)//從X部的V點(diǎn)找增廣路徑{ for(inti=1;i<=m;i++) { if(g[v][i]&&!visited[i])//找到未匹配邊

{ visited[i]=true; if(match[i]==-1||path(match[i])==1) { match[i]=v;//路徑取反操作

return1; } } } return0;}二分圖匹配例題BOJ1155找增廣路徑二分圖匹配例題BOJ1155求最大匹配

cnt=0;//最大匹配數(shù)

memset(match,-1,sizeof(match));for(i=1;i<=n;i++){memset(visited,0,sizeof(visited));cnt+=path(i);}二分圖匹配例題BOJ1155求最大匹配Asteroids題意：有一種超級(jí)武器，能摧毀一行或一列上的物體，現(xiàn)在有n*n的圖，k個(gè)物體，最少多少次摧毀。思路：覆蓋問(wèn)題，用最少的線覆蓋所有的點(diǎn)，二分圖匹配，以點(diǎn)為邊，以行和列為點(diǎn)，有物體的點(diǎn)的行和列連邊，進(jìn)行二分圖最大匹配。其他題目：pku146920602226Asteroids題意：有一種超級(jí)武器，能摧毀一行或一列上AirRaid題意：有n個(gè)點(diǎn)，k條有向邊，無(wú)環(huán)。求最少幾次將整個(gè)圖遍歷完，每個(gè)點(diǎn)只能走一次。思路：最小路徑覆蓋=n-最大匹配，構(gòu)造二分圖，求最大匹配。入點(diǎn)，出點(diǎn)構(gòu)成二分圖，若i，j之間有邊，則i的出點(diǎn)向j的入點(diǎn)連邊，每匹配一對(duì)點(diǎn)，說(shuō)明該路徑能覆蓋兩個(gè)點(diǎn)，所以最小路徑覆蓋數(shù)減一。相關(guān)：pku2594AirRaid題意：有n個(gè)點(diǎn)，k條有向邊，無(wú)環(huán)。求最少幾二分圖最佳匹配在二分圖中的每條邊都帶上一個(gè)權(quán)值，求權(quán)和最大的匹配就叫二分圖最佳匹配。具體模型BOJ上1080，1084就是非常赤裸的最佳匹配模型。求二分圖最佳匹配的算法。二分圖最佳匹配在二分圖中的每條邊都帶上一個(gè)權(quán)值，求權(quán)和最大的KM算法給出每個(gè)頂點(diǎn)可行頂標(biāo)lx,ly，對(duì)于所有邊e(i,j)都有l(wèi)x[i]+ly[j]>=w[i][j];對(duì)于所有邊e(i,j)在M中，都有

lx[i]+ly[j]==w[i][j];則M是G