摘要：?最大流可以看做是把一些東西從源點(diǎn)s送到匯點(diǎn)t，可以從其他的點(diǎn)中轉(zhuǎn)，每條邊最多只能輸送一定的物品，求最多可以把多少東西從s送到t，這樣的問題就是最大流問題。
最大流可以看做是把一些東西從源點(diǎn)s送到匯點(diǎn)t，可以從其他的點(diǎn)中轉(zhuǎn)，每條邊最多只能輸送一定的物品，求最多可以把多少東西從s送到t，這樣的問題就是最大流問題。
節(jié)點(diǎn)1為源點(diǎn)，節(jié)點(diǎn)5位匯點(diǎn)
每一條邊上的數(shù)字即為這條邊最多能輸送的數(shù)量，也稱為容量。（對(duì)于不存在的邊，容量為0）
這個(gè)圖能夠求出的最大流為24。
這時(shí)，實(shí)際運(yùn)送的物品量即為流量。
有些邊的流量不一定等于容量，也就是還可以在這條路上再流多幾個(gè)物品，這時(shí)，容量減去流量的值，即為殘量
殘量會(huì)單獨(dú)構(gòu)成網(wǎng)絡(luò)，但不一定聯(lián)通s和t，這樣的網(wǎng)絡(luò)稱作殘量網(wǎng)絡(luò)。
那么，應(yīng)該怎么求最大流呢？
這里介紹一個(gè)最基礎(chǔ)的算法，增廣路算法。
在圖上，從s開始，任意取一條路來走，走到t，增加流量。重復(fù)這樣的操作。但是很快，我們可以發(fā)現(xiàn)，這樣的做法不一定是最優(yōu)的做法。所以，我們要給它一個(gè)改進(jìn)的機(jī)會(huì)。
在圖上建立反向弧，將容量設(shè)置為0，當(dāng)從節(jié)點(diǎn)u流向節(jié)點(diǎn)v時(shí)，反向弧的流量也相應(yīng)等于這條弧的流量的相反數(shù)。
那么，通過搜索，每一次尋找一條路徑，使得流向匯點(diǎn)的總流量增加，這個(gè)過程叫做增廣，走過的路為增廣路。
可以證明，通過這個(gè)過程，經(jīng)過多次的增廣，必然會(huì)陷入不能增廣的情況，這時(shí)，流向匯點(diǎn)的總流量即為最大流。
只要?dú)埩烤W(wǎng)絡(luò)中s和t是連通的，必然會(huì)得到一條增廣路徑。
找路徑最簡單的辦法就是用DFS，但是對(duì)于一些具有刁鉆數(shù)據(jù)的網(wǎng)絡(luò)流題目，DFS可能會(huì)空間溢出或者超時(shí)，所以使用到BFS，也就是題目中說的Edmonds-Karp算法。
代碼模板（來自算法競(jìng)賽入門第二版（劉汝佳））：
structedge{intfrom,to,cap,flow;? ? edge(intu,intv,intc,intf):from(u),to(v),cap(c),flow(f){}};structEdmonds_Karp{intn,m;vectoredges;//邊數(shù)的兩倍vectorg[maxn];//鄰接表，g[i][j]表示節(jié)點(diǎn)i的第j條邊在e數(shù)組中的序號(hào)inta[maxn];//當(dāng)起點(diǎn)到i的可改進(jìn)量intp[maxn];//最短路樹上p的入弧編號(hào)voidinit(intn){for(inti=0;iq;? ? ? ? ? ? q.push(s);? ? ? ? ? ? a[s]=inf;while(!q.empty()){intx=q.front();q.pop();for(inti=0;i<(int)g[x].size();i++){? ? ? ? ? ? ? ? ? ? edge&e=edges[g[x][i]];if(!a[e.to]&&e.cap>e.flow){? ? ? ? ? ? ? ? ? ? ? ? p[e.to]=g[x][i];? ? ? ? ? ? ? ? ? ? ? ? a[e.to]=min(a[x],e.cap-e.flow);? ? ? ? ? ? ? ? ? ? ? ? q.push(e.to);? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? }if(a[t])break;? ? ? ? ? ? }if(!a[t])break;for(intu=t;u!=s;u=edges[p[u]].from){? ? ? ? ? ? ? ? edges[p[u]].flow+=a[t];? ? ? ? ? ? ? ? edges[p[u]^1].flow-=a[t];? ? ? ? ? ? }? ? ? ? ? ? flow+=a[t];? ? ? ? }returnflow;? ? }}EK;
版權(quán)聲明：本文內(nèi)容由互聯(lián)網(wǎng)用戶自發(fā)貢獻(xiàn)，版權(quán)歸作者所有，本社區(qū)不擁有所有權(quán)，也不承擔(dān)相關(guān)法律責(zé)任。如果您發(fā)現(xiàn)本社區(qū)中有涉嫌抄襲的內(nèi)容，歡迎發(fā)送郵件至：yqgroup@service.aliyun.com?進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，本社區(qū)將立刻刪除涉嫌侵權(quán)內(nèi)容。
用云棲社區(qū)APP，舒服~
