问题标签 [network-flow]

对于最大流量问题，似乎有许多非常复杂的算法，至少有一种算法是在去年才开发出来的。Orlin 的Max 在 O(mn) 时间或更短的时间内流动，给出了在 O(VE) 中运行的算法。

另一方面，我最常看到实现的算法是（我并没有声称已经进行了详尽的搜索；这只是偶然的观察）：

• 埃德蒙兹-卡普，O(VE^2)
• Push-relabel, O(V^2 E), or O(V^3) 使用 FIFO 顶点选择
• Dinic 算法，O(V^2 E)

具有更好渐近运行时间的算法对于现实世界中的问题规模是否不实用？另外，我看到很多算法都涉及“动态树”；这些曾经在实践中使用过吗？

我正在寻找一种在双向图中找到中国邮递员电路的算法。这里的双向图不是对称有向图，而是 Edmonds & Johnson 在 1970 年引入的图。

根据 Harold N Gabow 在 983 年发表的一篇论文，我发现很少有解决类似问题的论文，但没有正式的算法；他们刚刚提到这个问题可以减少/与完美的 b 匹配、双向网络流......等等有关，到目前为止我还无法理解。

如果有人知道这个概念和算法，请给我一些建议。

让 G = (V, E) 是一个网络，其中 s 和 t 是源和汇。设 f 是 G 中的最大流。找到一个算法来确定 G 中是否存在唯一的最小割。

我设法在这个网站上找到了一个类似的问题：

确定最小切割的唯一性

那里给出的答案摘要：

在残差图中找到从 s 可达的所有顶点，我们在 G 中找到了一个最小割 (S,T)。

查看相同的残差图，从 t 开始。以箭头的相反方向查看从 t 可到达的顶点组（表示可以到达 t 的所有顶点）。

这组也是最小切。

如果该剪辑与您的原始剪辑相同，则只有一个。否则，您只找到了 2 个剪辑，所以原来的剪辑不可能是唯一的。

我不明白为什么如果剪辑与原始剪辑相同，那么剪辑就是独一无二的。谁能向我们保证没有其他最小切割？

提前致谢

我需要绘制一些流网络，如下所示：

有谁知道可以做到这一点的程序？

在图中，我需要找到两点之间的最短路径，并在途中访问一个检查点。另外，我只能访问每个顶点一次。我想它与网络流量有关，但我不知道如何实现。

有人可以帮我解决这个问题吗？该解决方案显然是使用网络流，但我对网络流不是很熟悉。网络流如何帮助您解决这个问题？

螃蟹是一个无向图，它有两种顶点：1 个头和 K 个脚，以及将头连接到每条腿的恰好 K 个边。（1 <= K <= T，其中 T 是给定的）

给定一个无向图，您必须在其中找到一些顶点不相交的子图，其中每个子图都是螃蟹。目标是选择这些螃蟹，使它们覆盖的顶点总数最大化。

注意：如果两个图没有任何共同的顶点，则它们是顶点不相交的。

前任 。输入

我正在自学最大流量，但出现了这个问题：

原来的问题是

• 假设我们有一个工作列表

  {J1，J1，...，Jm}

• 以及已申请的人员名单

  {P1, P2, P3,...,Pn}

• 每个人都有不同的兴趣，其中一些人申请了多个工作（每个人都有一份他们可以做的工作清单）

• 任何人不得从事超过 3 份工作。

所以，这个问题可以通过在下图中找到最大流量来解决

我理解这个解决方案，但是

问题的更难版本

如果加上这些条件呢？

• 简单版的前 3 个条件（工作和人员列表，每个人都有兴趣或能力列表）仍然相同

• 该公司仅雇用 Vi 人员担任 Ji

• 公司希望雇用尽可能多的人

• 一个人可以从事的工作数量没有限制。

我应该在图中做出什么改变，以便我的解决方案也能满足这些条件？或者如果我需要不同的方法，请告诉我。

在任何人说话之前，这不是功课。这只是自学，但我正在研究最大流量，问题出在那个区域，所以解决方案应该使用最大流量。

我应该使用什么算法来找到有下限但没有流量上限的有向图上的最小流量？比如这个简单的例子：

在文献中，这是一个最小成本流问题。然而，在我的情况下，成本与每个边缘所需的流量的非零下限相同，因此我将问题表述为上述问题。在文献中，问题是：找到单源/单汇有向无环图的最小成本流的最佳算法是什么，其中每条边具有无限容量，流的非零下限，以及成本等于流量的下限。

从我的研究看来，人们处理任何类型网络的任何类型的最低成本的主要方式是将问题设置为LP 类型的问题并以这种方式解决。然而，我的直觉是，没有流量上限，即具有无限容量的边缘，会使问题变得更容易，所以我想知道是否有一种算法专门针对这种情况，使用比单纯形法等更多的“图形”技术. 人。

我的意思是，如果所有成本和下限都是 1，如上...然后我们正在寻找一个覆盖所有边缘的流，遵守流规则，并且不会通过从 s 到 t 的任何路径推动过多的流. 对我来说，这只是感觉它不应该需要 LP 求解器，事实上，维基百科关于最小成本流的文章指出“如果消除容量限制，问题就会简化为最短路径问题”，但我认为他们正在谈论下界全为零的情况。

还有开源 C/C++ 代码可以在任何地方实现最低成本吗？通过谷歌搜索可用的内容，我发现我可以自己将问题设置为 LP 问题并使用开源 LP 求解器进行求解，或者我可以使用 LEMON，它为最小成本流提供了几种算法。据我所知，boost 图形库不包含实现。

还有别的事吗？

Ford-Fulkerson 和 Edmonds-Karp 等。人。从零流量开始并增加它，直到它不能再增加。在正容量的情况下；但是，保证初始零流量既是合法流量，又是满足容量约束的流量。

对于负容量，全零的流量分配将无法满足容量约束，因此无法将其扩充为最大流量。

我在互联网上读到有人建议，负容量的最大流量可以作为两个最大流量问题来解决，但一直无法弄清楚如何去做......

我试图在http://www.spoj.com/problems/FASTFLOW/上解决这个问题

我想dinic的算法适合这个问题。但它在 O(EV^2) 时间内运行，这在最坏的情况下对于这个问题来说太慢了。对于不同的算法或改进该算法的运行时间有什么建议吗？

编辑：我包括我对 dinic 算法的实现。显然，它包含一些错误......任何人都可以提供一些测试用例或帮助调试程序的逻辑。