假设首先有一个未加权的图。我们在此图中有一个源，我们希望将值为 1 的流发送到之前指定的特殊节点，因此您必须权衡边。如果你把所有的边都设为无穷大，你可以这样做，但我们希望边的权重最小。
我的解决方案：首先我放置另一个源并将源连接到边缘等于 1 的特殊节点，并且图中的其他边缘具有无限值。然后在图中运行 Ford Fulkerson 算法。执行此算法后，每条边都有一个流，我将边的流设置为该边的权重。但这并不能使边缘的重量最小。
这个问题是如何解决的？这与一个著名的问题有关吗？
问问题
101 次