问题标签 [network-flow]

我有一个房间，每周开放几天，每天在不同的时间（7：00-14：42，...）

我有多个学生，每个人都可以在不同的日子、不同的时间参观房间（学生可能有时间在多天内参观房间）

我需要按照以下规则将所有（或最多）学生分配到房间：

• 每个学生每周必须访问房间一次，时间为 50 分钟
• （仅）第二个学生进入房间后，房间将在接下来的 20 分钟内不可用

第二条规则的例子：

我该如何解决这个问题？我曾想过在网络中使用流，但我遇到了一个问题。

假设我有这个流程。当学生连接到时间时，流程应该通过所有包含时间的组。如果这些组中的任何一个被占用，则流量无法流向那里。因此，当学生连接到时间时，所有可能与学生时间重叠的时间都将被禁用。但我不知道如何建立一个允许这样做的算法。

你能告诉我如何制作一个算法来完成这项工作吗？我不知道该怎么做。谢谢！

首先，我想澄清一下我已经看到了：Finding 'bottleneck edges' in a graph

这不是重复的，只是一个不幸的巧合，那个人错误地将最小切割称为“瓶颈”。

瓶颈边缘是流网络中的边缘，当它增加时，会增加网络的最大流量。

所以这不一定是最小切割，就像在像 o-1->o-1->o 这样的图的情况下，我们没有瓶颈边缘，但我们确实有一个最小切割。

（在该示例中，o 是节点，边是 -*->，其中 * 是某个整数。）

无论如何，因此找到所有瓶颈显然可以在 O(V+E) 中完成，（假设图形以邻接表表示形式给出），我认为这样做的方法是创建两个大小为 V 的数组，其中我将调用 INCOMING 和 OUTGOING，然后遍历邻接列表的每个元素两次，第一次将 INCOMING[i] 增加进入每个节点的边的值，第二次增加 OUTGOING[j] 的值在每个节点中，其中 j 是我们正在读取的邻接列表的节点，而 i 是邻接列表中的边要到达它的节点。

我认为这在 O(V+E) 时间内有效，但我觉得我的解决方案肯定更加复杂且难以解释。有没有更好的解决方案（不比 O(V+E) 更好，但更简单？）

我NetworkX用来实现一些论文。（其实 Networkx 不是必须的。如果有更好的库可以解决这个问题，你能推荐一下吗？）我的图表看起来像这个图像Automated_Planar_Tracking_the_Waving_Bodies_of_Mul

我给所有节点正权重。当我使用max_flow_min_cost(G, S, E)函数时，函数会返回类似的路径

那是因为这些是最大流量的路径。

但我想要的是流经所有节点且总成本最低的路径。例如：

所以，我决定使用min_cost_flow()函数。并且需要节点的需求。当然，我不能使用这种方法，因为我不知道从节点 'S' 开始会有多少条路径。

有什么办法可以解决我的问题吗？

总而言之，我想要一些方法来找到通过所有节点的路径，并且这些路径的总成本是最低的。

我的母语不是英语，这可能会让你感到困惑。如果您对此有任何疑问，请告诉我。

我看到使用 Ford-Fulkerson 和 BFS/DFS 的网络流的时间成本需要 O(V|E|)，因此 E 是增广路径。

如果有变量，学生 n，教师 m 和作业 l，我如何根据 n、m 和 l 计算时间复杂度？

O(V|E|) 是否包括循环部分的运行时间，例如当用户输入学生/教师/作业的数量时？

如何将这个多源流网络转换为单源流网络并找到其中的最大流量？

我们得到一个网络流量，以及网络中的最大流量。如果以任意正数增加其容量，则边缘将被称为增加边缘，也会增加最大流量。

提出一种算法，找到一个增加的边缘（如果存在）并以 $O(n^2)$ 运行。

我想到了以下想法——

• 找到图中的最小割，因为它是用福特-富尔克森算法给我们的。
• 将切口左侧所有边的容量增加 1。
• 在残差网络中运行 BFS 以查找是否存在改进的路径。如果存在，我们将拥有越来越大的优势。要找到它，我们必须将原始网络与新网络进行比较。我们必须这样做 n 次，因为每次我们将容量增加 1 时都必须检查改进的路径。

是否正确，我是否符合所需的运行时间？

谢谢！

所以我最近开始研究网络流量（最大流量、最小切割等），网络流量的一般问题总是涉及将某事物的“n”分配给另一事物的“k”。例如，我如何在一个拥有“k”个学校的城市中为“n”个孩子建立一个网络流，使得孩子们的家在学校的 x 公里范围内（为简单起见，我们只说 1 公里）？

如果我要进一步增加限制，例如每所学校不能有超过 100 名学生怎么办？还是300名学生？有人可以帮助我如何最初设置我的算法来解决这些问题（也希望有任何参考资料）？他们往往会出现在过去的期中考试/考试中，所以我只是想做好准备

我正在尝试解决来自 tardos 的以下问题。任何建议或帮助将不胜感激。

您被要求帮助一些网络管理员诊断他们网络中的故障程度。该网络旨在将流量从指定的源节点 s 传送到指定的目标节点 t，因此我们将其建模为有向图 G = (V,E)，其中每条边的容量为 1，其中每个节点至少位于从 s 到 t 的一条路径上。

现在，当网络中的一切顺利运行时，G 中的最大 st 流的值为 k。然而，目前的情况——以及你在这里的原因——是攻击者已经破坏了网络中的一些边缘，因此现在没有使用剩余（幸存的）边缘从 s 到 t 的路径。由于我们不会在这里讨论的原因，他们认为攻击者只破坏了 k 个边，这是将 s 与 t 分开所需的最小数量（即最小 st 切割的大小）；我们会假设他们相信这一点是正确的。网络管理员正在节点 s 上运行一个监控池，它具有以下行为：如果您发出命令 ping(v)，对于给定的节点 v，它将告诉您当前是否存在从 s 到 v 的路径。（所以 pint(t) 报告当前不存在路径；另一方面，ping(s) 总是报告从 s 到它自己的路径。）由于出去检查网络的每个边缘是不切实际的，他们希望通过明智地使用这个监控工具来确定故障的程度平命令。所以这就是你面临的问题：给出一个算法，向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 访问的完整节点集。当然，您可以通过 ping 网络中的每个节点来执行此操作，但您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。) 由于外出检查网络的每个边缘是不切实际的，因此他们希望通过明智地使用 ping 命令来确定使用此监控工具的故障程度。所以这就是你面临的问题：给出一个算法，向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 访问的完整节点集。当然，您可以通过 ping 网络中的每个节点来执行此操作，但您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。) 由于外出检查网络的每个边缘是不切实际的，因此他们希望通过明智地使用 ping 命令来确定使用此监控工具的故障程度。所以这就是你面临的问题：给出一个算法，向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 访问的完整节点集。当然，您可以通过 ping 网络中的每个节点来执行此操作，但您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。他们希望通过明智地使用 ping 命令来确定使用此监控工具的故障程度。所以这就是你面临的问题：给出一个算法，向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 访问的完整节点集。当然，您可以通过 ping 网络中的每个节点来执行此操作，但您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。他们希望通过明智地使用 ping 命令来确定使用此监控工具的故障程度。所以这就是你面临的问题：给出一个算法，向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 访问的完整节点集。当然，您可以通过 ping 网络中的每个节点来执行此操作，但您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，允许您的算法根据先前 ping 操作的结果来决定接下来要 ping 哪个节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。给出一个算法，向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 到达的完整节点集。当然，您可以通过 ping 网络中的每个节点来执行此操作，但您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。给出一个算法，向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 到达的完整节点集。当然，您可以通过 ping 网络中的每个节点来执行此操作，但您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。但是您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。但是您希望使用更少的 ping 来执行此操作（假设仅删除了 k 个边）。在发出此序列时，您的算法可以根据先前 ping 操作的结果来决定下一个要 ping 的节点。给出一个仅使用 O(k log n) ping 即可完成此任务的算法。

据我了解，Ford-Fulkerson 算法可以找到流网络中从源 ( s) 流到汇 ( t) 的最大流量。
但是有没有一种算法可以找到所有可能的提供最大流量的路径集？

一个例子：
在下面的这个网络中，所有边的容量都是 1。不难看出 from sto的最大流量t是 3。但是如何找到承载该流量的路径组合？

预期输出：
路径集 1：s-0-1-t, s-2-3-t, s-5-6-t
路径集 2：s-0-1-t, s-2-4-t, s-5-6-t
路径集 3：s-0-3-t, s-2-4-t, s-5-6-t
路径集 4：s-0-4-t, s-2-3-t, s-5-6-t

此处提出了类似的问题，但似乎没有得到明确的答案。

鉴于 N 个城市和 M 个规划的基础设施项目，我需要找到一种方法来确定两个特定城市将连接的最早日期。

一些城市位于同一个岛上，因此可以很容易地相互到达。这些城市形成了一个社区。有 C 个这样的社区。

示例输入：

由城市组成的社区：

• 切斯尼、本特利、迪
• 伊米、卡莉、金利
• Ady、Georgette、Elaina、Tanya

计划中的基础设施项目：

• 2020-04-12：本特利和金利之间的隧道
• 2021-01-04：迪伊和金利之间的桥梁
• 2021-07-01：Immy 和 Ady 之间的隧道
• 2021-10-12：Chesney 和 Georgette 之间的隧道。

例如，给定城市 Chesney 和 Georgette，这些城市连接的最早日期是 2021-07-01。

我正在考虑可以对这个问题建模的两种方法。要么作为一个图问题，所以它可以使用 MST 算法或通过将其简化为网络流来解决。我看到 Airline Scheduling 问题的一些相似之处，可以使用网络流来解决，这让我认为这个问题更可能是网络流问题。但是，我不太确定如何将此特定问题建模为网络流量问题。有人可以指导我正确的方向吗？