計算網絡的最大流量

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

使用與S等於源（我們假設源具有無限的in_capacity）的初始呼叫。