variable-assignment - 分配prob流网络解决方案

Question

我有成本矩阵 C 的分配问题，例如：

21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31

其中 C[i][j] 表示工人 i 完成工作 j 的成本。

如何使用网络流算法解决这个问题？我欢迎任何提示。

Answer 1

如果您仍在寻找解决方案，您可以将其解决为最小成本流问题：

1. 创建一个源节点，通过容量为 1 且成本为 0 的边连接到您的 N 个工作人员
2. 通过容量 1 和成本 C[i][j] 的边将每个工人 i 连接到每个作业 j
3. 最后将每个作业连接到容量为 1 且成本为 0 的汇节点

您的问题相当于最小化将 N 个流单元通过网络从源点推到汇点的成本。