问题标签 [ford-fulkerson]

我已经使用 Ford-Fulkerson 实施了一个解决方案来解决分配问题

假设有多个人想要参与多项活动的系统。每个人都有一份他们想做的活动列表，但只能分配一个。每个活动都有一个容量并分配给一个经理。每个经理都有他们可以监督的最大人数。

我通过将“源”节点连接到每个容量为 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 个工作），算法/代码将如何变化？

我知道 ford fulkerson 的运行时间一般是 O(f*(n+m)) 其中 f* 是网络的最大流量，而 n ， m 是网络中的顶点和边的数量，但是什么如果所有边缘容量都以常数 C 为界，这将如何影响运行时间？

还是会影响运行时间？

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

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

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

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

我得到了一个控制流图，其中自然数表示边缘容量，并通过运行 Ford Fulkerson 找到了最大流量。如果发生以下情况，我被要求找到一种快速算法来更新最大流量： 1. 一条边 e 发生变化，其容量增加 1 2. 一条边 e 发生变化，其容量减少 1

对于第一种情况，给定边 e=(u,v)，在图中放置另一个边 e'=(u,v) st e' 的容量为 1。然后在图上再次运行 FF，并且根据 FF 的定义，如果存在从 s 到 t 的另一条路径，它将找到另一条路径并更新最大流量。

我的问题是：为什么这与仅使用原始图运行 FF 不同，而是将 e 的容量更改为 e+1？

对于 2. 的任何帮助或指导，我也将不胜感激，因为我不知道该去哪里。

我正在尝试使用 Ford-Fulkerson 解决数学问题，但我遇到了一些问题。

这就是问题

我需要找到员工的最佳配置 - 工作职位，以确保每个工作职位都有一名具有合适角色的员工在那里工作（每个职位一名员工）。

我尝试使用此算法http://www.geeksforgeeks.org/maximum-bipartite-matching/

我建立了一个矩阵，其中每个员工都有一行，每个工作职位都有一个列。如果 X 员工可以在 Y 位置工作，我在 X 行、Y 列输入值 1，否则我输入 0。

上面的算法用 PHP 重写，在员工数量 <= 职位数量之前运行良好。

如果我的员工比职位多，算法计算时间往往会发散到无限大。

下面是算法代码：

一切都类似于上面链接中的算法，除了我传递了 $cols 数组，其中包含列的索引（因为它们是位置 ID，而不是数字排序的）。

这就是我创建矩阵的方式：

所以我只在员工和职位匹配的地方放 1。

任何人都知道如何解决这个问题？提前致谢

我需要帮助实现以下调度问题的有效算法。

明天有n病人来医院体检，但只有2位医生（A医生和B医生）。每次健康检查需要一个医生的时间段。如果可能，我需要将这些n患者分配到n仅使用 1 名医生的时间段。如果不可能有 1 名医生，我最多可以分配 2 名医生，因为只有 2 名医生可用。如果2个医生还不够。简单输出impossible

我将患者的可用性作为输入。比如有5个病人，1号病人只在1、2、5时段可用，2号病人在3、4时段可用，3号病人在1号时段可用……以此类推.

在这种情况下，我只需要一名医生来完成这项工作。输出

如果我得到如下输入：

然后我需要分配两个医生，因为 P3 和 P4 在可用性方面存在冲突。输出：

解决此类问题的最有效算法是什么？我该如何为此实现福特富尔克森算法？

到目前为止我所做的。

我试图将每个患者的可用时间段存储到单独的数组中。

按长度对数组进行排序。首先为患者分配最少可用时间段。

分配患者后，删除其余数组中的此时间段并再次按长度对数组进行排序。

重复此过程，直到分配所有患者。

我认为这就像最大流问题的无向图版本。

所以对于每条边 a->b，b->a 也是有效的。它的双向。他们共享相同的容量。这意味着如果我在两个顶点 a、b 之间的容量为 10，并且我有从 a 到 b 的流量为 5，那么从 a 到 b 的剩余容量以及从 b 到 a 的剩余容量将是 5。

我对此的解决方案是有一个从 b 到 a 的有向边和另一个从 a 到 b 的有向边。问题是，如果我在残差图中从 a->b 减少残差，我是否仍会增加后向边 b->a 的残差？

// 我创建了这个作为福特 fulkersion 算法的一部分

//下面这个循环中的问题（逻辑不工作）如果有人有解决方案请帮忙！

//------------------------------------------------ ----------

}