betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ JOI プログラミング 競技プログラミング お題箱より。JOIの解説記事は初めてかな…？ K - 遺産相続 解説途中の証明についてのリクエストだったのでそこを重点的に書きます。 解法 最大全域木として考える 都市を「頂点」、鉄道を「辺」、鉄道の収益を「辺重み」と考えます。 「閉路ができない範囲で取れるだけ取る」という処理は最小（最大）全域木のアルゴリズムで実現できます。まず子供1の辺の取り方は、 辺を重みが大きい方から順に見ていく。 それぞれの辺について、それを追加することで閉路ができないならば、その辺を取る。 というクラスカル法のアルゴリズムで求めることができます。重みが相異なるという条件から、この取り方は一意です。 子供2以降は、自… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F11%2F03%2F154228" title="JOI春合宿2015 K - 遺産相続 - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20%28a%2C%20b%29 Hatena Blog https://hatena.blog 2019-11-03 15:42:28 rich https://betrue12.hateblo.jp/entry/2019/11/03/154228 1.0 100%