找到仅在每行和列中仅选择一个矩阵（NXN）的最小总和

Question

这是与动态编程有关的另一个算法问题

这是问题：

找到给定矩阵的最小总和，以便在每行和列中选择一个总和

例如 ：

3 4 2

8 9 1

7 9 5

至少一个：4 + 1 + 7

我认为解决方案是网络流（最大流量/分钟），但我认为它不应该像它那样难

我的解决方案：单独到n列表[列]，列1，列2 ...列N

然后启动点（S） - > column1-> column2-> ... - >列n->（e）终点并实现最大流量/最小切割

Answer 1

这是 分配问题 可以将其视为最小重量完美匹配的特殊情况。解决任务问题的经典方法是使用 匈牙利算法.