DevFish Asked: 2024-02-25 08:16:12 +0800 CST2024-02-25 08:16:12 +0800 CST 2024-02-25 08:16:12 +0800 CST 如何更新最大流量模型 772 我试图理解这个问题 b 部分的答案。具体来说,我想知道为什么它是正确的,以及如何证明时间复杂度是O(V+E)。这是一个硬件问题,我在网上找到了这个答案,但我很难理解为什么它是正确的,并且不想只是复制它。非常感谢! algorithm 1 个回答 Voted Best Answer Luatic 2024-02-25T08:53:11+08:002024-02-25T08:53:11+08:00 如果边缘上的流量比容量小 1,则该流量仍然是有效的最大流量,并且无需执行任何操作。 那么我们来看看现在流量违反容量的情况。另外,我们假设(原始)网络已连接,即存在一条 st 路径(否则“最大流量”将为 0)。 这个想法基本上是“撤消”Ford-Fulkerson 的(假设)迭代,以消除容量违规,以一个单位流量为代价返回到有效的最大流量。 让我们看看边 (u, v)。因为我们有容量违规,所以我们有流量。该流量必须来自 s,因此存在一条 su 路径,沿着该路径我们有正流量 - 至少一个单位,因为我们的流量是整数。 由于流量保持,该单元也必须到达水槽,因此沿着该路径还有一条具有正流量的 vt 路径(同样至少有一个单元)。总体而言,这意味着必须存在一条 (u, v) 上的 st 路径,至少有一个单位的流量在该路径上流动。 例如,您可以通过以下方式找到此路径:从 u 运行 BFS,沿着具有正流的边跟踪前驱,以查找 su 路径;然后从 v 运行 BFS,沿着具有正流的边跟踪后继项,以查找 vt 路径。通过使用BFS,我们可以确保两条路径不交叉(如果交叉,我们可以剪掉交叉的部分)。 我们可以将这条路径上的流量减少 1。通过这样做,我们消除了容量违规,但我们现在可能有一个次优的流量 - 也许有一种替代方法来发送不使用此边缘的流量单位。 要解决此问题,您可以使用新容量和现在有效的流程运行另一次迭代。如果你找到一条增广路径,你(只能)恰好增增 1 个单位(你不能增增更多,否则你会得到比边缘具有更多容量的较少约束问题的所谓最佳解决方案更好的解决方案)。 至于时间复杂度: 找到 st 路径的时间复杂度为 O(V + E):您运行 2 个 BFS。BFS 必须在最坏的情况下考虑每个节点和每个边缘,因此没有办法解决这个问题。 找到增广路径,或者确定不存在增广路径,也是 O(V + E),这也是 BFS 的时间复杂度。
如果边缘上的流量比容量小 1,则该流量仍然是有效的最大流量,并且无需执行任何操作。
那么我们来看看现在流量违反容量的情况。另外,我们假设(原始)网络已连接,即存在一条 st 路径(否则“最大流量”将为 0)。
这个想法基本上是“撤消”Ford-Fulkerson 的(假设)迭代,以消除容量违规,以一个单位流量为代价返回到有效的最大流量。
让我们看看边 (u, v)。因为我们有容量违规,所以我们有流量。该流量必须来自 s,因此存在一条 su 路径,沿着该路径我们有正流量 - 至少一个单位,因为我们的流量是整数。
由于流量保持,该单元也必须到达水槽,因此沿着该路径还有一条具有正流量的 vt 路径(同样至少有一个单元)。总体而言,这意味着必须存在一条 (u, v) 上的 st 路径,至少有一个单位的流量在该路径上流动。
例如,您可以通过以下方式找到此路径:从 u 运行 BFS,沿着具有正流的边跟踪前驱,以查找 su 路径;然后从 v 运行 BFS,沿着具有正流的边跟踪后继项,以查找 vt 路径。通过使用BFS,我们可以确保两条路径不交叉(如果交叉,我们可以剪掉交叉的部分)。
我们可以将这条路径上的流量减少 1。通过这样做,我们消除了容量违规,但我们现在可能有一个次优的流量 - 也许有一种替代方法来发送不使用此边缘的流量单位。
要解决此问题,您可以使用新容量和现在有效的流程运行另一次迭代。如果你找到一条增广路径,你(只能)恰好增增 1 个单位(你不能增增更多,否则你会得到比边缘具有更多容量的较少约束问题的所谓最佳解决方案更好的解决方案)。
至于时间复杂度: