[AOJ] GRL_7_A Bipartite Matching

二部マッチング

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A&lang=jp

二部グラフの最大マッチング問題です。グラフ系の問題は苦手というよりも、知識がほとんど無いので、問題と解答をセットで覚えていきたいです。

方針

蟻本のp.197のコードを利用します。

注意する点は、 \( x_i, y_i\) の値の範囲が被ることがあるので、隣接リストを作るときは、\( (x_i, |X|+ y_i) \) とします。

詳しい内容は、ネットワーク系の問題を理解してから考え方を書きたいと思います。その内容を記述する日が訪れるかは微妙ですね。

ソースコード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする