問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196簡単に言えば木が与えられてどっかのノードからスタートして全ての辺を取り壊していく話。
解法
どの辺を何回通るか、というのを考えると、葉とつながってる辺は1回、普通の辺は行きと帰りと撤去で３回、スタート地点とゴール地点によっては行きと撤去の２回、の３通りがある。２回の辺をできるだけ多くしたいけどこれの最大値=木の直径*2
になっている。
木の直径は簡単に求められる。
登録:
コメントの投稿 (Atom)
-
概要 焼きなまし法 は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられていま... -
競プロで道具として用いられる様々な賢いアルゴリズムやデータ構造の多くは, 非常に賢い研究者たちによって発見されており, ほとんどは理論計算機科学の論文として国際学会の会議録や学術雑誌の形として出版されています. ここではアルゴリズム系の研究論文がよく出てくる様々な国際会議を紹介し...
-
0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで...
0 件のコメント:
コメントを投稿