hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/E 前提知識 二重辺連結成分分解 考察過程 1. 橋である辺と橋でない辺で挙動が分かれるのは見て分かる 2. 橋である辺を削除した場合の連結成分のコストを求めたい 3. 二重辺連結成分分解すれば良さそう 4. 分解後の成分を木として考えれば、dfsして累積和を取って連結成分のコストが求められる 5. 橋でない辺を削除したほうが最適な場合もあるので注意（その削除した辺のコストがあまりにでかい） 解法 https://onlinejudge.u-aizu.ac… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2018%2F09%2F23%2F115920" title="均衡な辺削除 (Balanced Edge Deletion) [Aizu Competitive Programming Camp 2018 Day 3 E] - はまやんはまやんはまやん" 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 2018-09-23 11:59:20 rich https://blog.hamayanhamayan.com/entry/2018/09/23/115920 1.0 100%