我们应该使用多少次福特富克森？
how many times we should used ford-Fulkerson?
我们给出了一个具有 K 个顶点的网络，并给出了 a 和 b。所有边的容量为infinite。对于从 a 到 b 的流，通过 max flow 的边称为瓶颈边，通过该边的传输流容量称为流瓶颈。给出了一个整数 M。我们想要大小为 M 且从 a 到 b 具有最低瓶颈的传输流。我们应该使用 ford-Fulkerson 多少次来计算这个流量？
O(1) 运行是答案，但是如何呢？
假设您为每条边分配一个容量 1，一次 运行 FF，并得到结果图。此外，令最大流量为M'。直观地，我们发现最小割是 $M'$，这意味着在这种情况下从 a 到 b 有 M' 条边不相交的路径。这告诉我们如何通过适当地缩放流来获得 ⌈ M / M' ⌉ 的解决方案。例如，假设 $M=5$，当将容量设置为 1 时，我们得到 $M' = 2$。然后我们知道 min-cut 是 2。如果我们将容量增加到 5 / 2 = 2.5，那么我们将刚好得到流量 5。由于这是一个非整数，我们会将一些边（形成从 a 到 b 的路径）的容量增加到 3，有些增加到 2。
你不能得到比刚刚发现的更低的东西。如果你能得到更低的东西，比如 M'' < ⌈ M / M' ⌉，那么如果你将所有边的容量设置为 M''，流量不会改变。根据最大流/最小割定理，这意味着存在 M / M'' > M' 边的最小割。这与最小切割仅为 M'.
相矛盾
我们给出了一个具有 K 个顶点的网络，并给出了 a 和 b。所有边的容量为infinite。对于从 a 到 b 的流，通过 max flow 的边称为瓶颈边，通过该边的传输流容量称为流瓶颈。给出了一个整数 M。我们想要大小为 M 且从 a 到 b 具有最低瓶颈的传输流。我们应该使用 ford-Fulkerson 多少次来计算这个流量？
O(1) 运行是答案，但是如何呢？
假设您为每条边分配一个容量 1，一次 运行 FF，并得到结果图。此外，令最大流量为M'。直观地，我们发现最小割是 $M'$，这意味着在这种情况下从 a 到 b 有 M' 条边不相交的路径。这告诉我们如何通过适当地缩放流来获得 ⌈ M / M' ⌉ 的解决方案。例如，假设 $M=5$，当将容量设置为 1 时，我们得到 $M' = 2$。然后我们知道 min-cut 是 2。如果我们将容量增加到 5 / 2 = 2.5，那么我们将刚好得到流量 5。由于这是一个非整数，我们会将一些边（形成从 a 到 b 的路径）的容量增加到 3，有些增加到 2。
你不能得到比刚刚发现的更低的东西。如果你能得到更低的东西，比如 M'' < ⌈ M / M' ⌉，那么如果你将所有边的容量设置为 M''，流量不会改变。根据最大流/最小割定理，这意味着存在 M / M'' > M' 边的最小割。这与最小切割仅为 M'.
相矛盾