基于最小费用最大流的优化交易问题：如何构建流网络？

现有$n$个物品$i_1,i_2,...,i_n$，当前持有$n$个物品，但存在重复和缺失情况，需最终恰好持有每个物品各一个。给定交易表指明物品兑换关系（示例如下），交易表中物品库存无限，但每次交易需支付1美元。需确定交易方案以最小化交易次数，若无法实现则需检测。

示例：$n=4$，当前持有$i_1=3,i_2=0,i_3=0,i_4=1$，交易表为$i_1\rightarrow i_2,i_2\rightarrow i_3$，需将2个$i_1$兑换为$i_2$，1个$i_2$兑换为$i_3$。

要求用最小费用最大流算法解决（不关注时间复杂度），请问如何构建对应的流网络？

按下面的步骤来构建最小费用最大流的网络模型：

1. 节点设置 #

• 新建一个源点S和一个汇点T。
• 为每个物品$i_k$创建两个节点：供给节点$U_k$（负责处理该物品的多余量）和需求节点$V_k$（负责处理该物品的缺失量）。

2. 源点到供给节点的边 #

先计算每个物品当前持有量与目标量（1个）的差值：

• 若当前持有量$cnt_k > 1$：说明有$cnt_k - 1$个多余的该物品，从源点S向$U_k$连一条边，容量设为$cnt_k - 1$，费用为0——这些是现成的多余物品，无需额外成本即可调出分配。
• 若当前持有量$cnt_k < 1$：该物品本身处于缺失状态，源点到$U_k$无需连边。

3. 供给节点到需求节点的边 #

• 每个物品的供给节点$U_k$向自身的需求节点$V_k$连一条边，容量设为无穷大（直接用$n$即可，足够覆盖所有可能的流量），费用为0——表示多余的该物品可以直接留存，无需交易。
• 根据交易表中的直接兑换关系，比如$i_a \rightarrow i_b$，从$U_a$向$V_b$连一条边，容量设为无穷大，费用为1——对应将1个$i_a$兑换为$i_b$需要1次交易（1美元成本）。
• 处理间接兑换的情况：先通过Floyd-Warshall算法计算任意两个物品之间的最小交易次数（即最短兑换路径的长度），只要$i_x$能通过兑换链得到$i_y$，就从$U_x$向$V_y$连一条边，容量设为无穷大，费用等于该最短路径的次数（比如$i_a→i_c→i_b$的费用为2）。

4. 需求节点到汇点的边 #

再次针对每个物品的需求情况处理：

• 若当前持有量$cnt_k < 1$：说明缺少$1 - cnt_k$个该物品，从$V_k$向汇点T连一条边，容量设为$1 - cnt_k$，费用为0——这是必须满足的需求总量。
• 若当前持有量$cnt_k > 1$：该物品无缺失需求，$V_k$到T无需连边。

5. 求解与结果判断 #

• 运行最小费用最大流算法，若从S到T的最大流总流量等于所有物品的缺失总量（即$\sum_{cnt_k <1} (1 - cnt_k)$），说明可以实现目标，此时的最小费用就是最少交易次数。
• 若最大流总流量小于缺失总量，则说明无法实现目标。

内容的提问来源于stack exchange，提问作者popcorn