最小费用最大流和Edmonds-Karp算法

为流量网络中的每一条边赋予一个单位流量代价,在求最大流的基础上求最小代价的问题称为最小费用最大流问题(一般也称为费用流问题)。

求最大流的Edmonds-Karp算法通过广度优先搜索寻找增广路。
求费用流时,将广搜改为SPFA,求一条总单位开销最小的增广路,这样就可以保证方案总开销最小的同时流量最大。

继续阅读“最小费用最大流和Edmonds-Karp算法”