從最小s-t切割中找出最大流量

Question

通過在殘差圖上使用來自源的BFS，給定最大流量f，很容易獲得最小容量的s-t切割。考慮到最小容量s-t減少，是否有算法獲得最大流量f？

Answer 1

不，基本上。問題在於一般情況下的分鐘告訴你很少。給定一個網絡，通過將一個新的弧從水槽附加到一個新的頂點變成新的水槽，形成一個新的網絡，容量等於舊的最大流量。現在最低限度就是這樣 - 沒有關於網絡其餘部分的信息。