max-flow

4热度

2回答

我必须编写一个程序，该程序需要在定向流图中保留一些数据。我需要在运行时计算最大流量。我知道存在几个用于处理图的库，实现几乎所有的经典算法，但我的问题是我的图是动态的，这意味着它在运行时会发生变化。每次演变后，我需要重新计算新的最大流量。的进化是，无论是：加入边缘增加的边缘和我需要重新计算是来自源的最大流量什么的容量S到在该步骤已被修改的边缘的目的地节点。例如： S

0热度

1回答

计算过流和最大流量算法

四溢，我在下面的链接阅读推流算法。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel 要提及的是用过流量 - 我们定义过量水流E为e（U）= F（V，U），所述气流成网Ú。甲顶点uεN- {S，T}的溢出/活性如果E（u）的> 0 我寻找例如用简单流网络我们如何计算E（u）的？感谢

2热度

1回答

计算广义网络中的最大流量

我试图找到一种高效的公开可用算法，最好是与实现一起使用，用于求解具有增益的广义（非纯）网络中的最大流量。所有乘数，容量和流量值都是非零整数。这样的算法是否存在，或者这个问题在多项式时间内是不可解的？

2热度

1回答

push flow relabel algorithm

V wrt中顶点的有效标记。一个预流x是一个函数d：N - >满足Z：[。] d [秒] = N^d [T] = 0 所有（V，W）属于E：d [v] < = d [W] + 1 假设我们有4个verticies包括（s和t）那么我们有d [秒] =根据我们应具有有效标记4 d [v] < = d [w] +1，但对于来自's'的边缘，它不是有效因为使用4 < = 1是错误的。这个逻辑不仅是源

1热度

1回答

分析

我被Cormen等读取推流算法在算法导论我具有其中提到如下理解引理26.20 difficulaty：设G =（ V，E）是具有源s和宿t的流网络，并且假设在G中是预流。然后，对于任何溢出顶点u，在残差网络Gf中存在从u到s的简单路径。要查看此leema的上下文可以在以下链接找到。 http://integrator-crimea.com/ddu0164.html 请您在此understad

0热度

1回答

将图书馆书籍分配给成员以使最大成员满意的算法

我在班级测试中遇到了问题。在一个图书馆里，每个成员要求四本书和每本书只有两个成员要求。此信息在二分图G =（X + Y，E）的形式给出 X：设置所有成员的Y：设置的所有书籍边缘E =边集（X，Y），其中x是书y所要求的成员。我们必须找到图书管理员可以给每个成员最多两本书的方式，以使最大成员满意。我想出了两种方法：引入了两个新的顶点S（源）和T（目标）。将边从s引入到X中容量为2的所有成员

4热度

1回答

如果每条边的容量增加，最大流量的变化

我需要找到一个线性算法（O（| V | + | E |），它可以找到原始最大流量已知的最大流量，但如果您知道mincut是什么，我想你可以只添加一个到最大流量为每切边每边加1

2热度

1回答

缺少埃德蒙兹卡普最大流算法一些路径

我实现Edmond Karp algorithm，但似乎这不是正确的，我没有得到正确的流量，可以考虑下面的图像和流4〜8：算法运行如下：首先发现4→1→8，然后发现4→5→8 后4→1→6→8 而且我觉得第三条道路是错误的，因为通过使用这条道路，我们不能使用从6→8流（因为它使用），而事实上，我们不能用4→5→6→8流。事实上，如果我们选择4→5→6→8，然后4→1→3→7→8，然后4→1