ei1333's page

割当問題(Hungarian)

説明

二部グラフの最小重みマッチングを求める. 最大を求めたいときは値を反転させる.

計算量

$O(N^2M)$

実装例

行列は 1-indexed なので注意すること. また $N \le M$ を満たす必要がある。