计算网络的最大流量

Question

我们能否找到一种算法（以线性时间）计算树状网络的最大流量，即对于删除汇（及其相关边）留下一棵树的网络。

Answer 1

是的，只需运行如下所示的代码：

maxf(s) {
  if (s == sink) return s.in_capacity;
  ret = 0;
  foreach(c in children(s)) ret += maxf(c);
  return min(ret, s.in_capacity);
}

使用 s 等于源的初始调用（我们假设源的 in_capacity 为无穷大）。

Answer 2

Ford-Fulkerson 的复杂度为 O(E*f)，其中 E 是边数，f 是最大流，如果问题中的 E 或 f 具有恒定的上限，则将其视为线性。