最大流问题

真的,资料好多的,转载两个差不多了,但其实,我是读运筹学教程+算法竞赛入门经典训练指南读懂的。

比较全面的是輝夜の永遠亭写的,基本上的流程都介绍了,特别是比较写得很好。

当然博客园上也有人转载http://www.cnblogs.com/longdouhzt/archive/2012/05/20/2510753.html

主要涉及以下:

1. Ford - Fulkerson 方法

2. Edmonds - Karp 算法

3. Dinic 算法

4. Improved SAP 算法

...

7. 算法效率实测!

不过算法具体来讲,这篇最大流dinic算法写得蛮好,虽然我是看书。。。

另外一个问题就是最小费用最大流问题,链接的博文我没怎么看,我看书的话,觉得核心就是,增广路的选择依据变成了找一条带权最短路(对应费用为路的权值),然后在图上加上这条路的增广容量。关键问题转化为找一条最短的增广路,书上用了另一个算法,叫Bellman-Ford算法,可以处理负权问题,但是解决不了负圈。

博文很短,写完了o(〃'▽'〃)o

原文地址:https://www.cnblogs.com/puluotiya/p/4745792.html