[AtCoder] ABC091 C – 2D Plane 2N Points

2D Plane 2N Points

https://beta.atcoder.jp/contests/abc091/tasks/arc092_a

二部マッチング問題です。

AOJの二部マッチングの問題と内容的には殆ど同じです。

二部マッチング問題

AOJの二部マッチングの問題を解くことができればこの問題も同じようにして解くことができます。下の記事でその解答を載せています。

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

考え方

隣接リストの部分は自分で作らないといけません。赤い点と青い点がそれぞれ \( N \) 個あるので、赤い点にそれぞれ \( 0 \) から \( N – 1 \) までの番号を振り、青い点にそれぞれ \( N \) から \( 2N – 1 \) までの番号を振ります。

赤い点 \( i \) と青い点 \( j \) に辺が張られる条件は、

\[ a_i < c_j \ \& \ b_i < d_j\]

です。このとき、\( (i, j) \) の辺ができます。これを全ての \( i, j \) について調べます。

あとは、最大マッチングを求めるアルゴリズムに投げます。

ソースコード

感想

この問題を解くためにAOJの問題を先に解いていました。解説では最大マッチングのアルゴリズムを使わなくても解けるそうなので、そちらの方も学ぶ必要がありますね。

ネットワーク系の問題は実際に手を動かして勉強する必要があるんですが、適切な教材がないので、アルゴリズムの活用だけにとどまっています。いつかはちゃんと勉強したいと思っています。

シェアする

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

フォローする