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

Question

ツリー状ネットワークの最大フローを計算するアルゴリズムを見つけることができます。つまり、シンク（およびそれに関連するエッジ）を削除すると、木。

Answer 1

Ford-FulkersonはO（E * f）です（Eはエッジの数、fは最大フローです）。問題のEまたはfに一定の上限がある場合、リニアと見なされます。

Answer 2

はい、ちょうど次のようなものを実行します。

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); 
} 

（私たちは、ソースが無限大のin_capacityを持っていると仮定）のソースに等しいsの最初の呼び出しを使用してください。