分配概率流网络解决方案

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. 创建一个源节点，通过边连接到您的 N 个工作节点
   容量 1 和成本 0
2. 通过容量 1 和成本 C[i][j] 的边将每个工作人员 i 连接到每个作业 j
3. 最后将每个作业连接到具有容量 1 和成本 0 的边的汇节点

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