问题标签 [ford-fulkerson]

我正在实现 Ford-Fulkerson 算法，但在增强阶段后更新图形时遇到了一些问题。我猜我的数据结构并不容易。

为了表示图表，我使用了这个：

也就是说，我在每个顶点关联它的传出边列表。

为了管理后向边，我为图中的每条边关联了一个“相反”边。

任何形式的建议表示赞赏。

边缘

顶点

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

为什么每次都选择最短增广路径而不是任意增广路径会使 Edmond Karps 算法比 Ford-Fulkerson 更快

网络中可以有多个最小切割。例如：

有四个最小切割，Ford-Fulkerson 找到一个“更接近” s（源）。我们可以对所有网络都说同样的话吗？也就是说，Ford-Fulkerson 找到离源最近的切口？如果为真，我们如何将流网络中“最接近源”的概念形式化？

我需要帮助来了解如何解决以下问题：

亚当教授有两个孩子，不幸的是，他们彼此不喜欢。问题是如此严重，以至于他们不仅拒绝一起步行上学，而且实际上每个人都拒绝在其他孩子当天踩过的任何街区上行走。孩子们在拐角处交叉的道路没有问题。幸运的是，教授的房子和学校都在拐角处，但除此之外，教授不确定是否可以将两个孩子送到同一所学校。教授有一张城镇地图。展示如何将确定两个孩子是否可以上同一所学校的问题表述为最大流量问题。

我唯一能想到的就是有一个四角图。左上角的顶点代表源（亚当的房子），右下角代表汇（学校）。右上角x的角代表邻域中的角，而y代表邻域的左下角。因此，我们有从S -> C1、S -> C2、C1 -> t和出发的路径C2 -> t。每条路径的权重为 1，因为它只能容纳一个孩子。该图的最大流量为 2，证明他们可以上同一所学校。

我遇到的问题是我不确定我找到的这个解决方案是否能解决问题。最让我难过的部分是我不确定这意味着什么：但事实上，每个人都拒绝在其他孩子那天踩过的任何街区上行走。如果两个人都住在同一个街区的同一个房子里，这句话怎么能说得通呢？

我有一个有向图

首先，我使用了 Ford-Fulkerson 算法来增加网络的流量。当我标记顶点时，我看到路径上的流：s->a->b->d->t可以增加一个，因此图形更改为：

我知道在搜索最大流量时，您需要将连接最小切割和图形外部部分的边的所有容量相加。我的最小切割包含 vertices: s, a, c，所以当我将所有边加起来时c(G, !G) = 3 + 2 +2 + 1，这比 flow to t5 要大得多。

我做错了什么，我搞砸了FF还是最小化了？

您如何修改 Ford-Fulkerson 算法以解决时间限制？例如，如果给你一个最大时间量，而每条边需要 1 个单位时间，你怎么能找到最大流量？

我正在研究最大二分匹配算法。我无法弄清楚如何根据地图中的键/值在数组中设置值。

最终我需要遍历我的行，这些行对应于我在地图 mymap 中的键。然后我需要根据 mymap 中的值将相应的列设置为 true (1)。最终它看起来像这样

目前我的算法看起来像这样，您可以看到我对如何遍历地图以在数组中设置适当的值感到困惑：

内联 void keep_window_open() {char ch; cin>>ch;} // 测试上述功能的驱动程序

// 上面这段代码有效

Ford-Fulkerson 算法是否会及时找到具有n顶点和m边的单位容量流网络（所有边都有单位容量）的最大流O(mn)？

我已经实现了 Ford Fulkerson 算法，现在正在尝试研究它的变体。

假设给定的图及其解决方案是

假设在导出解之后，其中一条边的容量增加或减少。我们需要找到一种算法来使用当前解决方案而不是从一开始就获得新的最大流量。

我的建议是，对于这个例子，如果我们假设 1-3 边的容量从 12 减少到 8，那么我们需要从 1 到开始节点进行 BFS，并将每个边上的流量减少 4 并且做一个 BFS 从 3 到 5 并减少那里的流量。但我不确定这是否正确。即使它是正确的，我也不知道如何实现它？

谁可以帮我这个事？