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

2019年5月16日

問題

方針

二部マッチング問題

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

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

コード

提出したコード

隣接リストの作成

  // 隣接リストの作成
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (a[i] < c[j] && b[i] < d[j]) add_edge(i, j + N);
    }
  }