[AtCoder] ABC 091 C – 2D Plane 2N Points

問題

方針

二部マッチング問題

基本的には、[AOJ] GRL_7_A Bipartite Matchingと同じようにして解くことができます。

頂点は与えられますが、辺がどのようになっているかは自分で実装しなければいけません。赤い点のラベリングを \( 0 \) から \(N – 1\) で与え、青い点を \( N \) から \( 2 * N – 1 \) で与えます。このとき、辺が張られる条件は、\( a[i] < c[j] \wedge b[i] < d[j] \) を満たす全ての \( i , j\) です。これは二重ループで求めることができます。

コード

提出したコード

隣接リストの作成