max-flow - すべてのエッジ キャパシティが増加した場合の最大フローの変化

Question

元の最大フローがわかっているグラフで最大フローを見つける線形アルゴリズム (O(|V| + |E|) を見つける必要がありますが、各エッジの容量は 1 増加します。

Answer 1

ミンカットが何であるかを知っているなら、各カットエッジの最大フローに1つ追加するだけでよいと思います。