二部グラフの最小重み最大マッチングは，左側に湧き出し，右側に吸い込みを置いて最小費用流問題を解くことで求めることができる．
また，左右の頂点数をそろえ，枝の無いところの辺コストを 0 とし，重みの符号を変えれば割り当て問題に帰着できるため，ハンガリアン法を適用することもできる．
略．
前原 貴憲(maehara@prefield.com).
Last Modified: 2007.10.20 04:52:56.
