标签：

10.9传输网(Transport network)

一些名词:

流量守恒(Conservation of flow)

除源点s(source)和宿点t(sink)之外，要求其他节点流入的流量和流出的流量相等

最大流(Maximal flow)

对付网络流图G，流量最大的可行流f，称为最大流

根基算法描述

最为朴素的算法，等于操作回溯法，，对所有可能的路径情况分析并取所有可能情况的最大值

基于贪心算法的思考，在最开始先找一可行流(feasible flow)，在此根本上上不停的寻找增广路径，直到再无增广路径；但是问题在于贪心寻找时不必然最优，故引入反向边的观点，操作这一思路到达回溯的感化以确保正确性；这就是这个算法的精华部分，操作反向边，使措施有了一个后悔和纠正的机会

因此得到如下根基算法:

找一可行流，对每条边的流量更新称残剩流量和反向流量

寻找增广路径，注意流量既可以走正向流量，也可以走反向流量；将总的流量值更新

反复过程2直至再无增广路径；此时得到的流量值即为最大流

最大流最小割定理

一言以蔽之，最大流即是最小割

编程算法实现

从寻找增广路径着手，可以深搜，广搜和一些其他记忆化操纵来帮助寻找增广路径，最常用高效的求最大流的算法:Dinic算法

10.9传输网(Transport network)