algorithm - 最佳流量分配

Question

我搜索了 stackoverflow 和谷歌，但没有找到遇到相同类型问题的人。

Optimal distribution of power plants on a city似乎是这个问题最接近的解决方案，但我相信我的问题比那里的问题更简单，因此会有比暴力破解更好的解决方案。

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

我尝试使用多个源和接收器解决网络流的这个问题，但它确实工作正常。

谢谢!

Answer 1

看this article .这就是您如何将问题减少到最小成本最大流量。

对于每个城市，计算需求 d作为usage - production .按 d=0 对城市进行分组, d<0和 d>0 .让所有的连接都有无限的能力。然后添加两个新节点，sink 和 source。在源和 d<0 之间添加边节点，容量 |d| .在 d>0 之间添加边和汇聚节点，容量d .现在你有了单源单汇网络，你可以应用任何最小成本最大流算法来找到解决方案。