问题标签 [max-flow]

我试图解决一个关于最大流量问题的问题。我有一个源和两个接收器。我需要在这个网络中找到一个最大流量。这部分是一般的最大流量。但是，在这个特殊版本的最大流量问题中，两个目标都必须获得相同的流量。

有没有人可以帮助我该怎么做？

我有 n 个使用旧系统完成的工作。如果我将它们更改为新系统，我将获得该工作的双重收益。一些工作对 (i,j) 具有依赖关系。改变工作但不改变其依赖对的成本 xij。作业 1 无法在新系统下运行。更改为新系统（当然不包括工作 1）以最大化收益的理想工作集是什么。

这是一个用我自己的话改写的算法问题。它应该减少到某种形式的最大流量或循环。由于成本取决于将其他作业更改为新系统（我似乎无法将静态值与最大流量图设置相关联并有一个可行的解决方案），因此我在提出一种方法时遇到了极大的麻烦。我已经考虑了一段时间，但仍在努力寻找一个体面的方法。任何有关如何考虑解决此问题的建议将不胜感激！

我正在尝试设计一种算法，该算法将模拟具有多个源和特定容量的多个汇的管道网络。

到目前为止，我已经尝试使用经典的 Ford-Fulkerson 算法，但我遇到的问题是这样的，给出下图：

给定S的源容量为 1，B 和 C的汇容量为 1 - a 流将导致 S - a - B，使 B 饱和为 1，而 C 流为 0。

我正在尝试在网络上均匀分配流量，以便B 和 C 都收到 0.5。有任何想法吗？

谢谢！

我正在阅读http://www.geeksforgeeks.org/maximum-bipartite-matching/和http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm并且无法理解。似乎这个例子是在假设每个工作只能接受 1 人并且每个人想要一份工作的情况下。我想知道如果 v 集的容量 > 1（可以为该工作雇用多个人）和 u 集 > 1（每个人想要超过 1 个工作），算法/代码将如何变化？

我已经编写了一个代码，用于从硬编码到 main 中的图形中获取最大流量。我按照指示进行操作，但我不断收到此错误，我不知道为什么。我试过改变很多部分和调试，但我想不通。这是错误：

这是我的代码：

这是 main 的精简版：

Ford Fulkerson 算法将在 O(|E|f) 时间内运行，其中 f 是最大流量；但是，有没有办法让它运行 O(|E|)？

使其运行小于 O(|E|f) 的解决方案之一是选择一条增广路径，该路径通过使用与通过加权最短路径问题等寻找路径相关的内容来最大程度地增加流量，但可以我保证它在 O(|E|) 时间运行？

基本上忽略找到增广路径所需的时间复杂度（即无论算法是什么，让复杂度为 O(1)）。

如果没有这种方法，反例是什么？如果是，我需要使用什么方法？

When implementing Ford-Fulkerson or Dinitz algorithms for maximum network flow there are two operations that need to be performed on the graph:

• Iterate over all neighbours of a given vertex
• Find the reverse edge of a given edge(this is needed for the graph modification when a flow is added along an augmenting path).

Ideally the first operation will be linear with respect to the number of neighbours and the second one should be constant. In addition the memory required for the graph representation should be linear with respect to the number of edges(note that for most practical applications of max network flow algorithms I have seen the number of edges is about linear times the number of vertices). All the estimations for the complexity for the two algorithms will only hold if the constraints above are met.

The problem is that none of the classical graph representations is able to meet the above requirements:

Adjacency Matrix

Using adjacency matrix, finding the reverse edge of a given edge can be done in constant time. However iterating over all neighbours is linear with respect to the number of all vertices and also the required memory is quadratic with respect to the number of vertices.

Edges list

Using this representation, iterating over all neighbours will not be linear with respect to the number of neighbours and also finding the reverse edge for a given edge is not constant.

Neighbours list

Using this representation we can iterate over all neighbours in linear time and also the needed memory is linear with respect to the number of edges. Still, finding the reverse edge for a given edge will be linear with respect to the number of neighbours of the destination vertex.

With a slight modification of this representation we could improve that - if instead of neighbours list we keep some binary search tree of the neighbours we could find the reverse edge with logarithmic complexity. And even better - if we use hash map instead of binary search tree we will have constant amortized complexity. Still this representation does not feel right - although still linear, a hash map has some memory overhead. Also it only has amortized constant complexity thus some operations may in fact be slower.

The question

So my question is: what graph representation is appropriate to implement maximum network flow algorithms?

我已经修改了最大流量问题的任务。我应该找到满足条件的最小流量（其中 f 是流量，c 是容量）：

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

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

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

问题：http ://www.spoj.com/problems/DIVREL

有问题的是，我们只需要从给定的一组元素中找到最大数量的元素不是倍数（a 可以被 b 整除）。如果我们只是从一个元素到它的倍数创建一条边并构建一个图，它将是一个 DAG。

现在问题变成了使用Dilworth 定理找到包含等于反链基数的所有顶点的最小链数，因为它是一个部分有序的集合。

可以使用二分匹配找到最小链（如何：它是最小路径覆盖）但现在我无法找到反链元素本身？

我必须在 C++ 中使用 maxflow 算法进行前景/背景分割。（http://wiki.icub.org/iCub/contrib/dox/html/poeticon_2src_2objSeg_2src_2maxflow-v3_802_2maxflow_8cpp_source.html）。我根据它们的 RBG 从 png 文件中获取像素数组，但下一步是什么。我怎么能用这个算法来解决我的问题？