基本概念：

網絡：（1）有一個源點 s 和匯點 t 。

? ? ? ? ? ?（2）每一條有向邊e=（u，v）都有一個容量限制記做c（e）。

流：定義在網絡弧集上的實值函數 f ，滿足三個性質

? ? ? ? ? ?（1）對任意的弧 0 <= f <= c(e)，容量限制。

? ? ? ? ? ?（2）f(u,v) == -f(v,u)，反對稱性。

? ? ? ? ? ?（3）流守恒性：除源匯點外，其余頂點都是過度點，流進頂點的流總和等于流出頂點的流總和。

殘余網絡：用e表示網絡中的邊，e' 表示殘余網絡中的邊，殘余網絡中的邊由以下兩種構成：

? ? ? ? ? ?（1）若f(e) < c(e) ，e=（u，v），則e' =（u，v）容量為 c(e) - f(e)

? ? ? ? ? ?（2）若f(e)>0，e=（u，v），則加入邊 e'=（v，u），容量為 f(e)

? ? ? ? ? ? ?其中有（1）生成的邊表示沿著這條邊還能推進多少流；由（2）生成的邊表示沿著該邊的逆方向能退回多少流。

增廣路： 定義增廣路 P 是在殘余網絡上的一條從源點 s 到匯點 t 的簡單路徑，路徑的殘余流量為該邊上的邊 e' 容量的最小值，其實就是殘余網絡上增廣的流值大于 0 的一條路徑。

?

割的定義：設網絡G，如果 X 是 V 的頂點子集，Y 是 X 的補集，即 Y = V - X，且滿足 源點 屬于X,匯點 屬于 Y。則稱K=（X,Y）為網絡 G 的割，K的容量記為 cap（K） 最小割就是該網絡中流量最小的割。

最小割最大流定理：

指在一個網絡流中，能夠從源點到達匯點的最大流量? 等于? 如果從網絡中移除就能夠導致網絡流中斷的邊的集合的最小容量和。即在任何網絡中，最大流的值等于最小割的容量

完整描述：下面給出的三個定理是等價的

（1）f 是 G 的最大流 （2）殘余網絡不包含增廣路徑? （3）對于圖的某個割K=(X,Y)，最大流=cap（K）

最大流問題：?在不超過個邊容量限制的情況下，求源點到匯點的最大流量

Ford-Fulkson算法思想：

（1）初始化網絡中所有邊的容量，c（u，v）表示邊的容量，c（v , u）=0 邊（v,u）為回退邊

（2）在殘量網絡中找一條從源點到匯點的增廣路P，找到進行（3）否則進行（5）

（3）在增廣路中找到路徑中容量最小的邊 X，累加到最大流中。

（4）將增廣路中所有的c（u，v）減去 X ，所有的c（v,u）加上X，構成新的殘余網絡，轉步驟（2）

（5）得到最大流，退出

《算法導論》中將Ford-Fulkson歸結為一種方法而非算法，也許正是因為（2）中為給出尋找增廣路的具體方法。

而能否高效的尋找到增廣路是判斷各算法優劣的主要依據。

根據劉汝佳大大在書中的建議：理解Ford-Fulkson算法的原理，比賽中使用Dinic或者ISAP（當做黑盒算法）

dinic模板鏈接：模板

最大費用最小流：每條邊除了有一個容量限制外，還有所需要的費用。而要達到的是總流量最大的前提下，總費用最小的流。

MCMF模板鏈接：模板?

轉載于:https://www.cnblogs.com/zhizhaozhuo/p/9594205.html

總結

以上是生活随笔為你收集整理的网络流 （网络流问题汇总）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。