algorithm - 各行と列で1つだけを選択する行列の最小合計（nxn）を見つけます

Question

これは、動的計画法に関連する別のアルゴリズムの問​​題です。

ここに問題があります：

各行と列で1つを選択するように、指定された行列の最小合計を見つけます

例えば ​​：

3 4 2

8 9 1

7 9 5

最小のもの：4 + 1 + 7

解決策はネットワークフロー（最大フロー/最小カット）だと思いますが、それほど難しくはないはずです

私の解決策：nに分離list [column]、column1、column2 ... column n

次に、開始点（S）->列1->列2-> ...->列n->（E）終了点で、最大フロー/最小カットを実装します

Answer 1

これは、グラフでの最小重みの完全一致の特殊なケースと見なすことができる割り当て問題です。割り当て問題を解決する古典的な方法は、ハンガリーのアルゴリズムを使用することです。