AOJ 1196 : 橋の撤去

橋の撤去 | Aizu Online Judge

ICPC諸島には島の数 n に対して n-1 個の橋があり,どの島から島へも, 橋を何回か渡れば到達することができるようになっている.

つまりになっている。

それが分かればあとはやるだけとなる。
すべての頂点(島)を根と見なして探索し、
・移動コストが一番大きな遷移(根まで戻りたくないので)、
・端っこ(橋を渡る必要がないので)
を考える。
すべての辺(橋)のコスト(長さ)を考えうる最大回数3でかけて足し、
「大きな遷移」を引き、「端っこ」につながる辺のコスト x2で引けばよい。

例えばSample Inputの2番目のケースを島1を根して考えると、

f:id:arukuka:20170614180905p:plain

最大の遷移(端っこは含めないことに注意)30と端っこの辺のコスト x2 = 12
を全体の合計 x3 = 196から引くと、
196 - 30 - 12 = 156
となる。なおこれは最小ではなく、島5か8を根にして考えたものが最小となる。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2369513#1