A Bangladeshi Contest at SUST（20151212）
UVa 13040
ある国には $N$ 個の街があって，$2$ つの街を繋ぐ双方向に通れる道が $M$ 個ある．
街 $i$ の座標 $(X_i,Y_i)$ が与えられる．
全ての道をちょうど $1$ 回通って旅をしたい．
どの街から初めて，どの街で終わっても良い．
ただし，不可能かもしれないので，それが可能なように，$2$ つの街をつなぐ高速道路を作ることができる．
高速道路を作るには，作る長さのユークリッド距離の $2$ 乗のコストが掛かり，一度作れば高速道路は何回でも利用しても良い．
最小コストを求める問題．
連結であるので，次数が奇数である頂点が高々 $2$ であれば全ての枝を通る経路が存在する．
よって，次数が奇数の頂点が $4$ 以上あるなら，うまく $2$ 頂点間に高速道路を作って，次数が奇数の頂点を $2$ 個以下にすれば良い．
ただし，直接 $2$ 頂点間に高速道路を作るのではなく，（コストは長さの2乗なので）途中で間の街を経由したほうがコストがかからないことがある．
よって，（自由が偶数の頂点も忘れないようにして）ワーシャルフロイドなどをして，各頂点間に高速道路を利用して移動するための最小コストを求めておく．
どこの頂点間に高速道路を作れば良いかは，動的計画法で求める．
状態を（まだ次数が奇数の頂点の集合）として，その状態にするまでの最小コストを計算する．
シュタイナー木のように，次数が偶数の頂点をうまく利用してコストを落とせることはなさそうなことは紙に書いて色々試してみるとわかる．
よって，$2$ つの次数が奇数のノードを繋いで，それらの次数を偶数にしていくのを繰り返せば良い．
時間計算量は $O(N^2 2^N+M)$ 程度．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月25日05時14分12秒
Last modified: 2015年12月16日01時56分32秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る
Logged in as: unknown user (not login)