この記事で使うアルゴリズム
プリム法
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/abc065/tasks/arc076_b
この問題は最小全域木を求めることで解くことができます。最小全域技の基本を理解するためにはまず下記の問題に取り組むことをオススメします。
方針
解説PDFを参考にすると良いでしょう。
- 最大で
N=10**5
であるため、愚直に最小全域木を求めることができません。 - 街と街の間にコスト
min(|a-c|,|b-d|)
の辺があるのではなく、コスト|a-c|
の辺とコスト|b-d|
の辺があると考える - x,y座標のうちどちらかに着目し、数直線上に街が並んでいると考える。この時、数直線上で隣接している街と街の間の辺さえ考えれば良い。(それらを足し合わせることで、離れている街同士の辺を表現できる)
- 最後にx座標についての考察で得られた辺の集合と、y座標のそれの和集合(辺の数は
2(N-1)
本となる)を考え、最小全域木を求めればよい。
コード
プリム法を用いて実装します。
1 | import heapq |
記事情報
- 投稿日:2020年4月28日
- 最終更新日:2020年5月8日