优化交易项目-最小成本最大流量

Question

有

n

项，。我有

n

项，但有些重复，有些丢失，我需要每项都只有一个。有一个交易表告诉您哪些物品可以与其他物品进行交易。例如：

项目	项目
1	2
2	5
4	3

交易表中的贸易物品库存无限。但每笔交易，您需要支付1美元。

现在我们想知道要交易哪些物品，以便最终我们只拥有每个物品一次，并最大限度地减少所需的交易（成本）。如果不可能，那么我们应该检测到它是不可能的。

示例：

，我们有 ，交易表是：。 我们需要将 2x i1 交易到 i2，将 1x i2 交易到 i3。

使用最大流最小成本算法解决问题。我对时间复杂度不是特别感兴趣。

如何构建图/流网络？

Answer 1

如何构建图/流网络？

这样的网络需要资源。来源是重复的项目。每个源的输出容量等于备件数量 ( count - 1 )

网络需要接收器。缺少的物品是水槽。每个接收器的输入都有一个容量，如果 1

交易表提供了其余的链接，每个链接都有无限的容量。

所以，对于你的例子，

应用 Edmonds-Karp 算法来获得答案 https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

如果流入任何汇的计算流量为零，则该问题不可行

总成本是通过内部链接的总计算流量（所有未连接到源或汇的图链接）