假设给定一个流网络 G=(V, E)，其中每条边的容量为 1。我想设计一个有效的算法来找到边 e，这样从 G 中删除它会导致 G' 的最大值较小（ s, t)-流量大于 G。
我想到了 G 的几个属性：
- 任何边的流都是二进制的；要么有流量，要么没有流量
- 增加一条边的流相当于在残差图上反转它
- 非零入边数 = 所有中间节点的非零出边数
- 改变 (s, t) 路径上的任何边会移除该路径中的所有流
除了运行 Ford-Fulkerson 并选择属于 min (s, t)-cut 的任何边之外，我想不出其他任何东西。
使用 G 仅包含容量为 1 的边这一事实，是否有更有效的算法？谢谢。