問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196簡単に言えば木が与えられてどっかのノードからスタートして全ての辺を取り壊していく話。
解法
どの辺を何回通るか、というのを考えると、葉とつながってる辺は1回、普通の辺は行きと帰りと撤去で3回、スタート地点とゴール地点によっては行きと撤去の2回、の3通りがある。2回の辺をできるだけ多くしたいけどこれの最大値=木の直径*2
になっている。
木の直径は簡単に求められる。
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます.
2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...
0 件のコメント:
コメントを投稿