algorithm - Compute Max flow for networks

Question

can we find an algorithm which computes (in linear-time) the maximum flow for tree-like networks, that is, for networks such that the removal of the sink (and its associated edges) leaves a tree.

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 有一个恒定的上限，这将被认为是线性的。