1

我已经修改了最大流量问题的任务。我应该找到满足条件的最小流量(其中 f 是流量,c 是容量):

f(u,v) >= c(u,v) 

因此,每个边缘的流量至少是边缘的容量。(我正在写容量,但它被重命名,因为它不再是容量,它的计数必须由流量来满足)

还有一件事。我有函数 MaxFlow,它给了我经典的最大流量,我可以调用它一次。

任何人都可以帮助我使用伪算法吗?我正在考虑修改 Ford-Fulkers 算法并根据我的需要进行更改,但我不确定在哪里适合 MaxFlow?当我知道图中的最大流量时,它如何帮助我使用算法?谢谢

4

1 回答 1

1

从具有下限的最大流量到最大流量有一个简单的减少:

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

这个想法是使所有边缘饱和。然后你就剩下不平衡的节点了。您可以使用最大流量算法来解决不平衡问题。

构造如下: 对于每个顶点 v,定义 M(v) := 传入边的下界之和 - 传出边的下界之和。删除所有下限并将每个原始边缘的容量设置为上限 - 下限(在您的情况下为无穷大)。

引入一个新的超级源 S 和一个新的超级汇 T。为每个顶点 v 添加一条容量为 M(v) 且 M(v) >= 0 的边 (S, v)。添加一条边 (v, T) M(v) < 0 的每个顶点 v 的上限容量 -M(v)。

解决由此产生的 ST 最大流量问题。

最后,移除 S 和 T 并将原始下界添加到每个原始边缘的流中。

于 2014-05-12T22:21:45.597 回答