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

Question

通过在残差图上使用来自源的BFS，给定最大流量f，很容易获得最小容量的s-t切割。考虑到最小容量s-t减少，是否有算法获得最大流量f？

Answer 1

不，基本上。问题在于一般情况下的分钟告诉你很少。给定一个网络，通过将一个新的弧从水槽附加到一个新的顶点变成新的水槽，形成一个新的网络，容量等于旧的最大流量。现在最低限度就是这样 - 没有关于网络其余部分的信息。