最大流
- 首先是網絡流中的一些定義：
- 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).一個簡單的例子.網絡可以被想象成一些輸水的管道.括号内右邊的數字表示管道的容量c,左邊的數字表示這條管道的目前流量f.
-
網絡流的三個性質：
1、容量限制: f[u,v]<=c[u,v]
2、反對稱性：f[u,v] = - f[v,u]
3、流量平衡: 對于不是源點也不是彙點的任意結點,流入該結點的流量和等于流出該結點的流量和。
- 隻要滿足這三個性質,就是一個合法的網絡流.最大流問題，就是求在滿足網絡流性質的情況下，源點 s 到彙點 t 的最大流量。
最小費用最大流
- 其他算法貝爾曼，spa，dinic
- Tarjan算法詳解
Reference
- 網絡流之最大流算法（EdmondsKarp
C/C++基本文法學習
STL
C++ primer