2015年5月3日日曜日

AOJ 1196 : 橋の撤去

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196
簡単に言えば木が与えられてどっかのノードからスタートして全ての辺を取り壊していく話。

解法

どの辺を何回通るか、というのを考えると、葉とつながってる辺は1回、普通の辺は行きと帰りと撤去で3回、スタート地点とゴール地点によっては行きと撤去の2回、の3通りがある。
2回の辺をできるだけ多くしたいけどこれの最大値=木の直径*2
になっている。
木の直径は簡単に求められる。

0 件のコメント:

コメントを投稿