水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

JOI '15 春合宿 4:1 - 遺産相続

問題

https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d4.pdf

解法

K 人それぞれに Union Find 木を構成し,辺のコストが高い順に辺を見ていく.辺ごとにどの人に辺を割り振るかを考える.この時,ある人を境に辺を含めることが可能になるので,その人を二分探索で探す.辺を含めることが可能になるかどうかの判定はそれぞれの人の Union Find 木で辺の両端が追加されているかどうかで出来る.O(MlogM).

解答

beta.atcoder.jp

二分探索の判定部で,どの人も辺を含めることが出来ない場合の処理を書いていなく,WA を連発してしまった.二分探索を単体で使うだけではない解法で使う方法を知った.

f:id:babcs2035:20181110134840p:plain