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

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

=0x∈Xv∈Vx∈X點集間的流量不包含s,t的點集，與它關聯的邊上的流量和為零x網絡中的割割（S,T）由兩個點集S,T組成，滿足

1、S+T=V 2、源點在S集合中

3、匯點在T集合中

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

5、c(S,T)表示割的容量最小切割時使c(S,T)最小的切割網絡中的割割（S,T）由兩個點集S,T組成，滿足割的流量任意割的流量等于網絡的流量證明：

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|割的流量任意割的流量等于網絡的流量割的流量網絡的流量小等于任意割的容量證明：

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

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

初始化流量網絡為0,則殘量網絡即初始為容量網絡.算法流程:

構圖->求最大流->輸出最大流最大流例題BOJ1154典型的最大流問題最大流例題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;//路徑標志

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

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

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

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求最大流最大流模型構圖對于求流網絡最大流的算法我們可以有現成的模板套用，在實際問題中，如何去構圖建立最大流模型才是解決問題的難點和關鍵。構圖一般考慮下面幾個要素: 1、問題是否符合求源點到目標點的所經過網絡的等效最大流。

2、找準源點和匯點

3、源點和網絡中的點，匯點和網絡中點的關系。

4、網絡中的個點的關系。

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

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

1、path的長度必為奇數，且第一條邊和最后一條邊為不匹配邊。

2、path經過路徑取反操作以后，得到比當前更大的匹配。

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

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

lx[i]+ly[j]==w[i][j];則M是G的最佳匹配KM算法給出每個頂點可行頂標lx,ly，對于所有邊e(i,二分圖最佳匹配先將一個未被匹配的頂點u做一次增廣路，記下哪些結點被訪問那些結點沒有被訪問。求出d=min{lx[i]+ly[j]-w[i,j]}其中i結點被訪問，j結點沒有被訪問。調整lx和ly：對于訪問過的x頂點，將它的可行標減去d，訪問過的y頂點，將它的可行標增加d。修改后的頂標仍是可行頂標，原來的匹配M仍然存在，相等子圖中至少出現了一條不屬于M的邊，所以造成M的逐漸增廣。二分圖最佳匹配先將一個未被匹配的頂點u做一次增廣路，記下哪些算法流程(1)初始化可行頂標的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標的值(4)重復(2)(3)直到找到相等子圖的完備匹配為止算法流程(1)初始化可行頂標的值二分圖最佳匹配例題BOJ1080題目意思非常清晰構圖非常明確,工作為X,人為YX到Y的權值已知求X到Y的最小匹配把X到Y的勸值改為負數,求最佳匹配后,再取負數,得到的就是最小匹配值.二分圖最佳匹配例題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;}/*可行頂標ly記為0，lx記為與x相連的邊的權最大值*/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()/*可行頂總結網絡流模型可以用來解決很多關于分配求最優(yōu)值得問題，它的最大流，最小費用最大流求解算法我們已經大概了解。在更多的實際問題中，網絡流模型的建立往往是難點。巧妙的建立一個模型往往能誕生一個優(yōu)質的算法?？偨Y網絡流模型可以用來解決很多關于分配求最優(yōu)值得問題，它的最Thankyou!網絡流算法介紹課件網絡算法介紹PPT網絡算法介紹PPT網絡流算法介紹1.基本概念2.最大流問題求解3.二分圖匹配4.二分圖最佳匹配關鍵詞：源點、匯點、容量、流量、殘量、費用、增廣路徑網絡流算法介紹1.基本概念關鍵詞：源點、匯點、容量、網絡流問題類比：求最短路徑 把實際問題的道路地圖抽象為有向圖，然后用一定算法求解最短路徑。 我們也可以將一個有向圖看作一個流網絡來解決另一類型的問題。 匹配問題、運輸問題、任務分配問題。。。網絡流問題類比：求最短路徑流網絡定義（FlowNetwork）V表示整個圖中的所有結點的集合.E表示整個圖中所有邊的集合.G=(V,E),表示整個有向圖.s表示網絡的源點,t表示網絡的匯點.對于每條邊(u,v),有一個容量c(u,v)(c(u,v)>=0)如果c(u,v)=0，則表示(u,v)不在網絡中。如果原網絡中不存在邊(u,v)，則令c(u,v)=0對于每條邊(u,v),有一個流量f(u,v).流網絡定義（FlowNetwork）V表示整個圖中的所有結流網絡示例水源源點S蓄水池匯點T水管/邊流速限制容量c流速/流量f流網絡示例水源蓄水池水管/邊流速限制容量c流速/流量f網絡流三個性質容量限制：f(u,v)<=c(u,v)對稱性：f(u,v)==-f(v,u)收支平衡:對于不是源點也不是匯點的任意結點,流入該結點的流量和等于流出該結點的流量和。只要滿足這三個性質,就是一個合法的網絡流.網絡流三個性質容量限制：f(u,v)<=c(u,v)網絡的流量、最大流一個合法的網絡流量|f|定義為：從源點流出的流量 ∑f(s,v)流向匯點的流量 ∑f(v,t)|f|的最大值表示為最大流網絡的流量、最大流一個合法的網絡流量|f|定義為：流網絡示例收支平衡容量限制f(v4,v6)=-f(v6,v4)=1f(v6,v4)圖中不給出網絡的流量|f|=5+3=8或等于5+2+1(匯點處)0<=|f|<=最大流流網絡示例收支平衡容量限制f(v4,v6)=-f(v6,殘量網絡對于網絡中的每一條邊，計算容量與流量的差即表示為殘量。R(u,v)=C(u,v)–F(u,v)形象的說，一條邊的殘量即為該邊還能流過的流量。殘量網絡對于網絡中的每一條邊，計算容量與流量的差即表示為殘量殘量網絡舉例v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原網絡殘量網絡殘量網絡舉例v1tsv2(2,2)(4,4)(2,4)(0,殘量網絡從殘量網絡中可以清楚地看到：因為存在邊(s,v2)=3,則知道從S到v2還可以再增加2單位的流量；因為存在邊(v1,t)=2,則從v1到t還可以再增加2單位的流量。v1tsv2232422殘量網絡從殘量網絡中可以清楚地看到：v1tsv2232422后向弧其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s還可以增加4單位的流量。但是從v1到s和原網絡中的弧的方向相反。這樣的弧稱為后向弧。問題：有必要建后向弧線？tsv232422v1后向弧其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s為什么要建立后向弧在尋找最大流的過程中，有些弧的選擇一開始可能就是錯誤的。所以在路徑中加上后向弧，作為標記。當發(fā)現了另一條可增廣的路徑是并包含后向弧，意味這條路徑對以前對這條弧頂選擇進行取消后向弧為算法糾正自己所犯的錯誤提供了可能性，它允許算法取消先前的錯誤的行為為什么要建立后向弧在尋找最大流的過程中，有些弧的選擇一開始可增廣路徑在殘量網絡中，從源點S出發(fā)到匯點T的一條路徑。增廣路徑上的最小殘量表示該網絡還可增加的額外流量。增廣路徑點集間的流量定義點集間的流量：f(X,Y)=∑∑f(x,y)則有：

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

=0x∈Xv∈Vx∈X點集間的流量不包含s,t的點集，與它關聯的邊上的流量和為零x網絡中的割割（S,T）由兩個點集S,T組成，滿足

1、S+T=V 2、源點在S集合中

3、匯點在T集合中

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

5、c(S,T)表示割的容量最小切割時使c(S,T)最小的切割網絡中的割割（S,T）由兩個點集S,T組成，滿足割的流量任意割的流量等于網絡的流量證明：

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|割的流量任意割的流量等于網絡的流量割的流量網絡的流量小等于任意割的容量證明：

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

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

初始化流量網絡為0,則殘量網絡即初始為容量網絡.算法流程:

構圖->求最大流->輸出最大流最大流例題BOJ1154典型的最大流問題最大流例題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;//路徑標志

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

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

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

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求最大流最大流模型構圖對于求流網絡最大流的算法我們可以有現成的模板套用，在實際問題中，如何去構圖建立最大流模型才是解決問題的難點和關鍵。構圖一般考慮下面幾個要素: 1、問題是否符合求源點到目標點的所經過網絡的等效最大流。

2、找準源點和匯點

3、源點和網絡中的點，匯點和網絡中點的關系。

4、網絡中的個點的關系。

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

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

1、path的長度必為奇數，且第一條邊和最后一條邊為不匹配邊。

2、path經過路徑取反操作以后，得到比當前更大的匹配。

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

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

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