问题标签 [network-flow]

假设我们有 m 个考试 E={E1,E2,...,Em} 和一组 I={I1,I2,...,In} 的工具，并且每个考试 Ej 需要 I 的 Rj 的一个子集。每次检查都有 Pj $ 利润，每个仪器成本 Cj $。我们想选择一些检查来最大化（利润总和 - 成本总和）。

我认为我们可以使用 LP，这样我们每次检查都有 m 个变量 Xi 并且 Xi = 0 或 1，我们的目标函数是：对于所有 i 和 j Xi(Pi) - (A)Cj 其中 A 是 xor 所有需要的 Xi Ij

但我不能通过网络流来模拟这个问题。我的问题是如何表达这样一个事实，即当我们选择考试并为其仪器付费时，我们可以将这些仪器用于其他考试。

假设我们有一个有向图并且每条边都有一个正容量。如果 C 是一个正常数，我说，如果我们将 C 添加或减去所有边缘容量，则最大流量会发生变化（可能会增加或减少）。我的问题是，为什么如果我们将所有边容量乘以 C，最大流量是 C 的乘积？

为什么这是真的？

我们有一个有向图（没有权重），G(V, E)，有两个顶点s，t使得 in-degree ofs和 out-degree oft等于0。我们想找到从s到的最大不同边路径数t。通过使用哪种算法，我们可以做到这一点。Bellman-Ford、Dijkestra、Huffman 和 Network Flow。我认为霍夫曼如此无关紧要，但其他人呢？我认为网络流是答案，但我不知道为什么？stackeeeers，请帮助我！

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

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

如何在这个无向图中找到最大流量？任何人都可以显示步骤吗？

我已经搜索了 stackoverflow 和 google，但我还没有找到有相同类型问题的人。

一个城市的发电厂的最佳分布似乎是最接近这个问题的解决方案，但我相信我的问题比那里的问题更简单，因此会有比蛮力更好的解决方案。

问题是这样的：我有 9 个城市，每个城市都在生产电力和使用电力。每个城市都与其他 8 个城市相连。我如何确定以最少的能量传输量将多余电力输送到需要它的城市的最佳方式？

我试图用网络流来解决这个问题，利用多个源和接收器，但它确实可以正常工作。

谢谢！

我很想利用网络流方法来解决这个问题。希望这里的人可以花时间帮助我为这个问题构建一个合适的图表。当解决最大流量时，构建的图应该导致作业机器分配最大化给定数量的机器和作业计划的作业数量。


给定 m 台机器和 n 个工作，约束 m≤n。使用网络流算法来解决分配给定机器数量的最大化作业。

每个作业Ji都有一个开始时间Si和完成时间Fi。所有机器都是相同的，一次最多只能完成一项工作。我们必须找到一个分配，以便我们可以安排最大数量的工作。

我尝试过的方法：-> 作业和机器在图中形成节点。
-> 从源到所有作业节点的边。
-> 从所有机器到终端节点的边缘。
->每个作业节点的中间节点，它具有来自每个重叠作业节点的传入边。
并停留在这里如何进一步进行。

我已经通过贪婪的方法制定了一个解决方案，我很想学习网络流方法。

PS：我已经通过贪婪的方法制定了解决方案。
问了同样的问题，并在没有任何解释的情况下被否决票击落因此重新提问，因为前一个问题由于投反对票而没有引起任何关注。

我正在开发一个拥有资源流网络的系统，这应该考虑时间。

例如：

考虑一个标准流网络，其中每个节点都是一个仓库，用于分发具有有效期的物品。此外，将一个项目从一个节点传输到另一个节点也需要时间，因此当一个项目从源发送时，它到达接收器之前的时间应该最小化。

网络包含源（供应商）和汇（客户），另外，节点（仓库）可能有库存，如果一个项目已经存在。

对这个项目的需求在不同的时间点分布在整个网络中，应该计算一个合适的流量。

但是，您可能会在时间线中间对现有流量网络的需求发生变化，从而迫使您更改网络中的流量。这样做时，我希望避免从一开始就重新计算所有内容，而只需对网络进行细微的更改，以便将新的需求考虑在内。

我看过标准流算法，很难找到任何以同样方式考虑时间的东西。我正在寻找能够将我推向正确方向的东西。

有谁知道解决此类问题或类似问题的任何算法？或者对处理时间方面的良好数据结构有什么建议？

graphviz 或其子项目是否支持 tcp 流类型图，例如：

我已经浏览了 graphviz 文档和图库，但没有什么能引起我的注意。

为什么是假的？

流量为何以及如何发生变化？

谢谢你。