问题标签 [ford-fulkerson]

嘿，我正在实施 ford-fulkerson 算法并找到最大流量。我只是从文本文件名中读取一些输入作为桥接并找到最大流量，但它显示索引 3 的错误超出长度 3 的范围。错误在第 24 行，它说的是我不明白为什么它显示错误. 任何人都请帮助解决这个问题。我已经尽力了，但我没有得到它的确切解决方案。

这是我的代码：

这是它显示的错误：

这是我正在阅读的输入文件：bridge.txt

我遇到了一篇文章，指出福特富尔克森算法的时间复杂度，通常由 O(M*F) 给出，其中 M = 边数，F = 最大流量，可以交替描述为 O(M *N )，其中 N = 顶点数，考虑没有重复边的图，其中每条边都有单位容量。

即，在上述情况下，推断为 O(M* F) = O(M* N)。因此 N 必须等于 F？

这是正确的，如果是这样，怎么可能？

我想知道福特富尔克森算法的剩余容量的前向和后向边缘将如何转换为矩阵？上三角矩阵是前边，下边是后边吗？

假设首先有一个未加权的图。我们在此图中有一个源，我们希望将值为 1 的流发送到之前指定的特殊节点，因此您必须权衡边。如果你把所有的边都设为无穷大，你可以这样做，但我们希望边的权重最小。

我的解决方案：首先我放置另一个源并将源连接到边缘等于 1 的特殊节点，并且图中的其他边缘具有无限值。然后在图中运行 Ford Fulkerson 算法。执行此算法后，每条边都有一个流，我将边的流设置为该边的权重。但这并不能使边缘的重量最小。

这个问题是如何解决的？这与一个著名的问题有关吗？

我试图理解为什么如果我在残差网络上运行 DFS 并发现有一个有向圆，这意味着在同一个网络上有多个可能的合法流函数具有相同的最大值。

谢谢你

我可以从二分图（间接） G=(V,E) 中删除的最小边数是多少，以便每个节点最多有一个度数？

我试图用定义流网络（和福特富尔克森算法）来做到这一点。但我不知道在这种情况下如何定义流网络。