使用Ford Fulkerson從流量中去除邊緣後有效計算最大流量

Question

假設已經使用Ford-Fulkerson計算出了G的最大流量，但現在已從E中移除了一條邊線，如何可以有效更新最大流量。

Answer 1

如果e卸下十字切割邊緣，則最大流量等於|f| − c(e)，其中|f|是先前計算的最大流量和c(e)是除去邊緣的容量。

你可以找到詳細的解釋here。