1

我正在做一个特定的练习，我被卡住了。

要解决：

解决流通需求问题。有些工厂生产货物，有些村庄必须交付货物。它们由道路网络连接，每条道路都可以容纳最大数量的货物通过它。问题是找出是否有满足需求的流通量。这个问题可以转化为最大流量问题。假设每个工厂节点 fi 都有一个生产率 pi。另外，那个di 是vi 村的需求率。您的输入将是使用其每个节点的邻接列表给出的图形。最初给出一个描述图节点数量的数字，然后是每个节点的邻接列表的一行（连同容量），例如“da 10 c 5”表示节点 d 连接到 a（容量为 10）和到 c（容量为 5）。

据我了解，我需要这样的输入文件：

10
a b 10 c 20
b c 5 d 10
d e 7 f 8
a 10
e -5

//nodes = 10  
//directed graph -> a to b with capacity 10, a to c with capacity 20  
//a production = 10, e consumption = -5

我已经得出结论，我应该使用 Ford-Fulkerson 算法来找到最大流量（因为这是要求的输出）

环顾算法的不同实现（我正在考虑使用 C 或 Java 对其进行编码），我偶然发现了以下问题：

Ford-Fulkerson 仅适用于 1 个源和 1 个接收器。在这个问题中，我们有测试用例，例如有 3 个工厂和 2 个村庄。有人可以启发我，因为我真的被卡住了。

4

1 回答 1

2

这是 1-source 1-sink Ford-Fulkerson 算法的典型扩展。本质上，您将另一个“虚构”节点U视为 1 源，并将该节点连接U到所有工厂。（即哪些是K您问题的根源）

同样，您将所有接收器（即村庄）连接到您添加到给定图中的M另一个虚构接收器节点。V然后，当您计算从U到的最大流量时V，您将计算出从所有工厂到所有村庄的最大流量。

V显然，应该考虑连接 U 和工厂的边的权重以及连接村庄的边的权重。在您的情况下，工厂的每个传入边缘都U应该具有等于该工厂容量的权重。在连接村庄到 的边的情况下，V不需要有界限，因此它可以与整个图中的最高权重一样高，或者可以表示无穷大的实际值。

于 2019-03-17T12:33:20.683 回答