算法 : max flow problem and s-t minimum cut

Question

设 G 是最大流问题的输入图。设 A 为最小 s-t 割在图中。假设我们将图中每条边的容量加 1。是不是一定A 仍然是最小割是真的吗？如果是则证明，如果不是则给出反例

[注:我认为答案是否定的，不一定，但我想不出反例]请注意，这是一道家庭作业题，我正在寻找提示或任何我可以获得的帮助:)

Answer 1

有了 user57368 的评论，很容易构造简单的反例。

例如V={A,B,C,D}, E={(A,B,2.5), (B,D,1), (C,D,1)}。最小割是 {(B,D), (C,D)}，权重为 2。

如果将权重 1 添加到每条边，您将得到 E2={(A,B,3.5), (B,D,2), (C,D,2)}。这是权重为 3.5 的最小割 {(A,B)}。