algorithm - 如何使用最大流量解决这个问题？

Question

C1 城市愿意出售一些商品，而其他 C2 城市愿意购买一些商品（每个城市都可以出售或购买商品，但不能同时出售）。每个销售城市只能向一个城市销售商品，每个购买城市只能从一个城市购买商品。

您的目标是以最大化交换商品数量的方式连接自私的城市。

最难的是每个城市只能向/从一个城市出售/购买商品的限制。

Answer 1

您将不得不使用最小成本最大流量来解决这个问题。在流量 1 的每两个城市之间添加一条边，并花费该城市对的最小买卖金额的负数。例如，如果您有出售城市 A 愿意单元格 X 单元和购买城市 B 愿意购买 Y 单元，则计算Z = min(X, Y)并在 A 和 B 之间添加一条边，流量为 1 和 cost -Z。