Area1 https://blog.hatena.ne.jp/Area1/ Area1のif(memo[i][j]) https://area.hateblo.jp/ SRM グラフ 問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10835&rd=14432街と村が存在し、それらの位置が与えられる。最初、村には道が通っていない。街と村の間に道路を引くか、街に行くことのできる村とそうでない村の間に道路を引くことでどの村も少なくとも一つの街に行けるようにしたい。道路敷設のコストは端と端との間のユークリッド距離である。コストを最小化せよ。 やりかた 普通に最小全域木すればいいような気もするが、街と街の間はつなぐ必要がないので工夫する必要がある。といっても街と街のあいだのコストを0にすればいいだけ。以下ソース。 cl… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Farea.hateblo.jp%2Fentry%2F2013%2F08%2F10%2F222759" title="SRM 503 Div2 Hard KingdomXCitiesandVillagesAnother - Area1のif(memo[i][j])" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-08-10 22:27:59 rich https://area.hateblo.jp/entry/2013/08/10/222759 1.0 100%