C - 2D Plane 2N Points

  • image
  • 考えたこと
    • 高々200の二部グラフ、辺を素朴に使っても10^4、何が難しいのか
    • あ、最大二部マッチングを最大流に帰着して解くことが一般的には難しいのか
  • 公式解説
    • 上記解法は「余談」として触れられてる
    • 想定解法はグリーディに決定する手段を見つけてO(N)

ARC092