本章代碼鏈接：https://pan.baidu.com/s/1zHHKvvAj3JPNbiDggYSO1g 提取碼：mphz
【網(wǎng)絡(luò)流是什么】
網(wǎng)絡(luò)流(network-flows)是一種類比水流的解決問(wèn)題方法，與線性規(guī)劃密切相關(guān)。
【概念·容量網(wǎng)絡(luò)】
容量網(wǎng)絡(luò): 設(shè) G(V, E)是一個(gè)有向網(wǎng)絡(luò), 在頂點(diǎn)集V 中指定了一個(gè)頂點(diǎn), 稱為源點(diǎn)(記為 S ), 以及另一個(gè)頂點(diǎn), 稱為匯點(diǎn)(記為T); 對(duì)于每一條弧∈E, 對(duì)應(yīng)有一個(gè)權(quán)值 c(u, v)≥0, 稱為弧的容量, 通常把這樣的有向網(wǎng)絡(luò) G 稱為容量網(wǎng)絡(luò)奥秆。
【概念·最大流問(wèn)題】
最大流問(wèn)題：給定一個(gè)有向圖G=(V,E)班眯，其中每一條邊(u,v)均有一個(gè)非負(fù)數(shù)的容量值休傍，記為c(u,v)≥0克婶。同時(shí)在圖中有兩個(gè)特殊的頂點(diǎn)悴灵，源點(diǎn)S和匯點(diǎn)T绿映，要求從源點(diǎn)S到匯點(diǎn)T的最大可行流量擒滑。
【概念·殘余容量】
定義cf(u,v)=c(u,v)-f(u,v)表示邊（u,v）的殘余容量腐晾，意思是該邊最多還能通過(guò)cf(u,v)的流量。
【概念·殘余網(wǎng)絡(luò)】
由殘余容量大于0的邊構(gòu)成的網(wǎng)絡(luò)
【概念·增廣路】
找出一條從S到T的路徑p丐一，使得路徑p上所有邊的cf(u,v)都
大于0藻糖。假設(shè)路徑p上最小的cf(u,v)等于k，那就可以使得S到T增加k
的流量库车。
【相關(guān)規(guī)定】
一般巨柒，每條有向邊上有兩個(gè)量，容量和流量柠衍，從i到j(luò)的容量通常用c[i,j]表示,流量則通常是f[i,j].注意洋满，這里的f(i,j)通常認(rèn)為是凈流，也即若i->j實(shí)際流量為p珍坊，j->i實(shí)際流量為q牺勾，則f(i,j)=p-q;（例：如果u到v有 4 單位的實(shí)際流及由v到u有 3 單位的實(shí)際流，那么f(u,v) = 1 及f(v,u) = ? 1）阵漏，
【性質(zhì)】
- 容量限制：對(duì)任意u,v∈V驻民，f(u,v)≤c(u,v)。
- 反對(duì)稱性：對(duì)任意u,v∈V履怯，f(u,v)=-f(v,u).從u到v的流量和從v到u的流量互為相反值回还。
- 流守恒性：除非u=s或u=t，否則Σf(u,w)=0（w∈V）即結(jié)點(diǎn)的凈流是零叹洲，除了“制造”流的源點(diǎn)和“消耗”流的匯點(diǎn)懦趋。
【EK算法】
EK算法，也即最短路徑增廣算法疹味，基于FF方法（Ford-Fulkerson方法）即增廣路方法仅叫。
增廣路方法是很多網(wǎng)絡(luò)流算法的基礎(chǔ)，一般都在殘留網(wǎng)絡(luò)中實(shí)現(xiàn)糙捺。其思路是每次找出一條從源點(diǎn)到匯點(diǎn)的能夠增加流量的路徑诫咱，調(diào)整流值和殘留網(wǎng)絡(luò)，不斷調(diào)整直到?jīng)]有增廣路為止洪灯。之所以正確是因?yàn)镕F方法的基礎(chǔ)是增廣路定理(Augmenting Path Theorem):網(wǎng)絡(luò)達(dá)到最大流當(dāng)且僅當(dāng)殘留網(wǎng)絡(luò)中沒有增廣路坎缭。這個(gè)思路十分容易理解，也不必證明签钩。
不斷地dfs/bfs尋找增廣路掏呼，記錄路徑上的邊以及路徑上所有邊中最小的殘余容量Min，路徑上每條邊容量減去Min铅檩，總流量加Min憎夷。直到無(wú)法找到即可。
【Dinic算法】
實(shí)際情況中EK算法的效率不理想昧旨，所以一般使用Dinic或ISAP等更高效率的算法拾给。EK算法每次尋找增廣路都是一條一條找祥得，而Dinic算法則是盡可能尋找多條增廣路，實(shí)現(xiàn)多路增廣蒋得。
算法步驟：
對(duì)殘余網(wǎng)絡(luò)進(jìn)行bfs分層级及，把起點(diǎn)s到結(jié)點(diǎn)u的距離d(u)看成u的層次。
dfs增廣额衙，增廣路沿著滿足d[v]=d[u]+1的邊（u,v）走饮焦。
重復(fù)直到找不到增廣路。
由于Dinic算法每輪進(jìn)行一次bfs窍侧，然后dfs增廣县踢， 每輪結(jié)束后源點(diǎn)和匯點(diǎn)不再連通，因此源點(diǎn)到匯點(diǎn)的最短路至少會(huì)加1疏之，最多有O(n)輪bfs，每條增廣路增廣至少使一條邊滿流暇咆，一輪最多增廣O(m)次锋爪，增廣路徑長(zhǎng)度O(n)，因此復(fù)雜度O（n^2 *m）爸业。然而這只是理論最壞復(fù)雜度其骄，實(shí)際上效率往往更優(yōu)。如果所有邊容量為1扯旷，可以證明Dinic算法時(shí)間復(fù)雜度為O(min(n2/3,m1/2) *m)拯爽，對(duì)于二分圖最大匹配這種特殊圖，復(fù)雜度為O(n^1/2 *m).
【ISAP算法】
菜雞沒學(xué)不知道
【最大流最小割定理】
對(duì)于一個(gè)網(wǎng)絡(luò)流圖G=(V,E)钧忽，其割的定義為一種點(diǎn)的劃分方式：將所有的點(diǎn)劃分為S和T=V-S兩個(gè)部分毯炮，其中源點(diǎn)s∈S，匯點(diǎn)t∈T耸黑。
定義凈流f(S,T) = Σf(u,v),u∈S,v∈T桃煎。
定義割的容量C(S,T)為所有從S到T的邊容量之和C(S,T) = Σc(u,v),u∈S,v∈T。
證明如下：
任意一個(gè)割的凈流f(S,T)都等于當(dāng)前網(wǎng)絡(luò)的流量f大刊，f(S,T) = f(S,V) - f(S,S).
從S到T的流等于從S到所有節(jié)點(diǎn)的流減去從S到S內(nèi)部節(jié)點(diǎn)的流为迈，f(S,T) = f(S,V).由于S內(nèi)部的節(jié)點(diǎn)之間存在的流一定有對(duì)應(yīng)的反向流，因此f(S,S)=0缺菌，f(S,T)= f(s,V)+f(S-s,V).
再將S集合分成源點(diǎn)s和其他屬于S的節(jié)點(diǎn)葫辐，f(S,T) = f(s,V).
由于除了源點(diǎn)s以外其他節(jié)點(diǎn)不會(huì)產(chǎn)生流（流量平衡）f(S-s,V)=0，f(S,T) = f(s,V) = f.
那么對(duì)于任意ST割有當(dāng)前流量f=f(S,T)<=C(S,T).
當(dāng)沿增廣路增廣的算法找不到增廣路時(shí)伴郁，把源點(diǎn)s能到的點(diǎn)歸為S集耿战，剩下V-S為T集，形成一個(gè)ST割焊傅。且對(duì)于任意的u∈S,v∈T昆箕，有f(u,v)=c(u,v)（如f(u,v)0鸦列，s可以到達(dá)v，與v屬于T矛盾）鹏倘。即當(dāng)前流量f=C(S,T)薯嗤，f<=任意C(S,T)的等號(hào)成立，即此時(shí)C(S,T)最小纤泵，為最小割骆姐，f最大，為最大流捏题。最大流=最小割玻褪。
看不懂沒關(guān)系，因?yàn)槲乙部床欢?/p>
【最小費(fèi)用最大流】
最小費(fèi)用最大流公荧，給原來(lái)網(wǎng)絡(luò)每條邊加上一個(gè)費(fèi)用值cost带射，表示每單位流量經(jīng)過(guò)該邊需要花費(fèi)cost，其反向邊費(fèi)用-cost循狰，意思是回流時(shí)減少花費(fèi)（退錢）窟社，在求解最大流的前提下，使總費(fèi)用最小绪钥。
解法：每次沿著最小花費(fèi)的增廣路增廣（白書有證明）一個(gè)簡(jiǎn)單的算法：Spfa費(fèi)用流灿里，由于圖有負(fù)權(quán)邊，用Spfa尋找最小費(fèi)用增廣路（由于Spfa算法的不穩(wěn)定程腹，有時(shí)可能被卡）
更快的算法：Dijkstra費(fèi)用流匣吊，ZKW費(fèi)用流。
