simezi_tan https://blog.hatena.ne.jp/simezi_tan/ simezi_tanの日記 https://simezi-tan.hatenadiary.org/ AOJ グラフ理論 問題 無向グラフが与えられる。ここから辺を一本取り除き、できた連結成分をA, Bとする。（A, Bの片方またはどちらも空かもしれない） グラフGに対してsum(G) = Σ{w(e)|e∈Gの辺}とする。ただしw(e)は辺eの重みである。 abs(sum(A) - sum(B))を最小化するような取り除くべき辺を求めよ。 複数ある場合は辞書順最小のもの。 制約 グラフの頂点、辺はともに10万以下。 重みは10^9以下の正の整数。 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsimezi-tan.hatenadiary.org%2Fentry%2F20180929%2F1538209339" title="AUPC 2018 day3 E: Balanced Edge Deletion - simezi_tanの日記" 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-29 17:22:19 rich https://simezi-tan.hatenadiary.org/entry/20180929/1538209339 1.0 100%