3

我正在尝试找到一种有效的、公开可用的算法，最好是通过实现来解决具有增益的广义（非纯）网络中的最大流量。所有乘数、容量和流量值都是非零整数。

是否存在这样的算法，或者这个问题不能在多项式时间内解决？

4

2 回答 2

1

以下是一些算法和一些解释的链接：

  1. http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm
  2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
  3. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2

这是我最大流量的解决方案：对不起我当时年轻的变量名称:) http://infoarena.ro/job_detail/431616?action=view-source
希望它有所帮助

于 2012-06-13T14:56:12.287 回答
0

第一个（强）多项式时间算法由 Végh 于 2013 年发布，此后由 Olver 和 Végh改进为 O(( m + n log n ) m n log( n ^2 / m））。但我不知道该算法的任何公共实现。

链接的论文还包含对早期（弱）多项式时间算法以及近似算法的引用，其中一些可能具有公共实现。（ Tardos 和 Wayne 的这篇较早的论文提到了 C++ 实现。）

于 2018-05-01T20:59:13.890 回答