algorithm - ネットワークの最大フローを計算する

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 is O(E*f) where E is the number of edges and f the maximum flow, which would be considered linear if you have a constant upper bound on E or f in your problem.