添加边缘后更新最大流量 [英] Update Maximum Flow After Adding an Edge

问题描述

考虑到我们有一个网络流量和使用Edmond-Karp算法，我们已经有了网络上的最大流量。现在，如果我们向网络添加任意边缘（具有一定容量），更新最大流量的最佳方法是什么？我正在考虑更新有关新边缘的残留网络，并再次寻找扩充路径，直到找到新的最大流量，但我不确定它是否有效或者它是最好的方法！

解决方案

在做maxflow之后，你知道每条边的流量。所以，当成本边缘改变了，你可以做以下的事情：

1. 假设边缘流动的内容是 w code>。


2. 现在做一个转发dfs 和一个向后dfs 从该边缘开始并且从其链接的边缘撤消总共 w 内容。

由 x / y 表示，其中 y 表示边缘容量， x 表示它所流动的内容。

现在您要更改边缘 4-> 3 从 2 到 3 。





你所要做的就是从 4-> 3 边缘和取消<$ $做一个向前和向后的dfs c $ c> 2 来自这些边缘的权重为 4-> 3 flowed w = 2 content。

这个过程如下所示： b
$ b

现在你快完成了：）

3. 将边缘 4-> 3 的成本由 2 到 3 ，然后再次尝试找到扩充路径：）
   

让我知道你是否觉得难以理解，或者我是否错了：）

编辑：

1. 如果新的边缘成本大于当前成本，那么您不必去除重量。你可以尝试找到一个改变边缘容量的增强路径。但如果容量减少了，你必须撤销重量并尝试找到一条增强路径。如果添加了新的边，可以添加边并尝试找到增大路径（如果可用）。而已。

Consider we have a network flow and using Edmond-Karp algorithm, we already have the maximum flow on the network. Now, if we add an arbitrary edge (with certain capacity) to the network, what is the best way to update the maximum flow? I was thinking about updating the residual network regarding the new edge and again look for augmenting path until we find new max flow, but I am not sure if it works or if it is the best way!

解决方案

After doing maxflow you know the amount of content each edge flowed.

So, when the cost of an edge changed you can do the following things :

1. Suppose, the content flowed by that edge is w.
2. Now do a forward dfs and a backward dfs from that edge and undone total w content from the edge it linked.

Here each edge is represented by x/y, where y means the edge capacity and x means the content it flowed.

Now you want to change the cost of edge 4->3 from 2 to 3.

All you have to do is do a forward and backward dfs from 4->3 edge and undone 2 weight from these edge as 4->3 flowed w=2 content.

Here is the process will look like :

Now you are almost done :)

3. Change the cost of the edge 4->3 from 2 to 3 and again try to find an augmenting path :)

Let me know if you find it difficult to understand or if i'm wrong somehow :)

Edit :

1. If new edge cost is greater than current cost than you won't have to undone the weight. You can just try to find an augmenting path changing the edge's capacity.

2. But if the capacity reduced, you have to undone the weight and try to find an augmenting path.

3. If a new edge added, you can just add the edge and try to find an augmenting path if available. that's it.

这篇关于添加边缘后更新最大流量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！