最大網(wǎng)絡(luò)流問題01網(wǎng)絡(luò)與流基礎(chǔ)網(wǎng)絡(luò)流問題定義與符號體系在有向圖G=(V,E)中，指定一個源點s和一個匯點t，源點是流量的起點，匯點是流量的終點。有向圖與源匯點每條邊(v,w)都有一個容量cap(v,w)，表示該邊能夠承載的最大流量。流量flow(v,w)是非負的，表示實際通過該邊的流量。容量與流量0流的存在性一個所有邊流量均為0的流稱為0流，0流總是存在，為后續(xù)可行流和最大流的討論提供了基礎(chǔ)?？尚辛髋c殘流網(wǎng)絡(luò)可行流必須滿足容量約束0≤flow≤cap和中間點流量平衡約束，即中間點的流出量等于流入量。可行流的約束條件殘流網(wǎng)絡(luò)G*與原網(wǎng)絡(luò)G有相同的頂點集，邊的容量根據(jù)原網(wǎng)絡(luò)的流量和容量計算，用于設(shè)計網(wǎng)絡(luò)流算法。殘流網(wǎng)絡(luò)的構(gòu)造02增廣路算法可增廣路與增廣定理增廣定理如果不存在可增廣路，則當前流為最大流。沿可增廣路調(diào)整流量可以增大總流量?？稍鰪V路是從源點s到匯點t的一條路徑，路徑上的向前邊非飽和，向后邊非零流?？稍鰪V路的定義Ford-Fulkerson框架與PFS實現(xiàn)Ford-Fulkerson算法框架通過反復(fù)尋找可增廣路并沿其增廣流量，直到找不到可增廣路為止。PFS算法優(yōu)先級優(yōu)先搜索PFS用于尋找可增廣路，可按容量或距離設(shè)置優(yōu)先級。算法實例最大容量增廣路和最短增廣路是PFS的兩種實例，適用于不同場景。010203復(fù)雜度與稀疏網(wǎng)絡(luò)表現(xiàn)01算法復(fù)雜度最短增廣路算法復(fù)雜度為O(nm2)，最大容量增廣路算法復(fù)雜度為O(mnlognlogM)。02稀疏網(wǎng)絡(luò)表現(xiàn)在稀疏網(wǎng)絡(luò)中，最短增廣路算法復(fù)雜度降至O(n3)，最大容量增廣路算法復(fù)雜度降至O(n2lognlogM)。03預(yù)流推進算法預(yù)流與活頂點概念預(yù)流的定義活頂點預(yù)流滿足容量約束，但中間點的流出量可以小于或等于流入量?；铐旤c是存流量大于0且不是源點或匯點的頂點。高度函數(shù)與可推流邊高度函數(shù)高度函數(shù)h滿足殘流網(wǎng)絡(luò)中h(u)≤h(v)+1且h(t)=0?？赏屏鬟吙赏屏鬟吺菨M足h(u)=h(v)+1的殘邊。通用預(yù)流推進流程01初始化時，源點的出邊流量設(shè)為容量，高度設(shè)為n。初始化02選擇活頂點，若存在可推流邊則推進，否則重標號。推進與重標號03當活頂點集合為空時，算法結(jié)束，得到最大流。算法終止基于頂點的FIFO實現(xiàn)FIFO隊列使用FIFO隊列管理活頂點，依次檢查每個頂點的出邊。復(fù)雜度該實現(xiàn)的復(fù)雜度為O(mn2)，但在實踐中表現(xiàn)良好。最高標號優(yōu)先與復(fù)雜度使用優(yōu)先隊列按高度選擇活頂點，優(yōu)先處理高度最高的頂點。01該算法的復(fù)雜度為O(n2√m)，在稠密網(wǎng)絡(luò)中表現(xiàn)優(yōu)異。

02復(fù)雜度最高標號優(yōu)先04模型變換與經(jīng)典應(yīng)用多源多匯到單源單匯超級源匯點增加超級源點s和超級匯點t，將多源多匯問題轉(zhuǎn)化為單源單匯問題。邊的容量超級源點到原源點的邊容量為原源點的供給，原匯點到超級匯點的邊容量為原匯點的需求。可行流判定與兩階段框架循環(huán)流通過(t,s)無限邊將帶下界問題轉(zhuǎn)化為循環(huán)流問題。兩階段框架第一階段求可行流，第二階段在殘量網(wǎng)絡(luò)上繼續(xù)增廣至最大流。二分圖最大匹配歸約增加源點s和匯點t，原邊方向從X指向Y，容量為1。網(wǎng)絡(luò)構(gòu)造網(wǎng)絡(luò)的最大流對應(yīng)二分圖的最大匹配，流量為1的邊即匹配邊。最大流與匹配頂點容量約束等價性新網(wǎng)絡(luò)的最大流與原網(wǎng)絡(luò)的最大流相等。將帶容量的頂點拆分為兩個頂點，中間邊的容量為原頂點的容量。頂點拆分表格數(shù)據(jù)取整應(yīng)用01網(wǎng)絡(luò)構(gòu)造構(gòu)造網(wǎng)絡(luò)，行節(jié)點和列節(jié)點分別對應(yīng)表格的行和列，邊的容量為上下界。02取整結(jié)果網(wǎng)絡(luò)的可行流對應(yīng)表格的取整結(jié)果，滿足行和列的約束。05算法選型與應(yīng)用容量范圍與稀疏度權(quán)衡算法選擇經(jīng)驗閾值根據(jù)容量范圍和網(wǎng)絡(luò)稀疏度選擇合適的算法，預(yù)流推進在稠密網(wǎng)絡(luò)中表現(xiàn)更好。給出以n=1e4、m=1e5、M=1e9為界的經(jīng)驗選型閾值，幫助快速決策。代碼復(fù)用與實現(xiàn)要點通過統(tǒng)一的殘量網(wǎng)絡(luò)接口，實現(xiàn)代碼復(fù)用。01建議使用鄰接表和迭代器，避免不必要的性能開銷。

02實現(xiàn)技巧統(tǒng)一接口常見陷阱與調(diào)試技巧反向邊初始化錯誤、高度函數(shù)設(shè)置錯誤等是常見的實現(xiàn)陷阱。常見錯誤通過殘量打印、活頂點監(jiān)控等方法快速定位問題。調(diào)試方法06小結(jié)近線性與并行化進展理論突破近年來，容量Scaling結(jié)合預(yù)流推進算法已接近線性時間復(fù)雜度。并行化在多核和GPU環(huán)境下，通過并行化技術(shù)可顯著加速算法運行。最小費用與多商品流多商品流多商品流引入線性規(guī)劃列生成思想，適用于復(fù)雜網(wǎng)絡(luò)資源分配。最小費用流通過勢函數(shù)和約簡費用轉(zhuǎn)化為迭代最短路問題。最小費用流可行流滿足容量約束和流量平衡的流。