uva117

UVA の The Postal Worker Rings Once を解いた．

題意は，与えられた連結グラフにおいて，全ての辺を少なくとも一度通る閉路のうち最小となるコストを出力せよ．

ただし奇数次の頂点は高々 2 つ．

サンプル入力のグラフを図にするとこんな感じ:

だいぶバグって情けない感じだったけど，通しました． まず入力をコード上で使い易い形に落とすのが面倒だった…．

さて，「奇数次の頂点が高々2つ」という条件がキモ．つまり与えられるグラフは（準）オイラーグラフ．

ということで，グラフの種類により場合分けすれば良い．

オイラーグラフ

ある頂点から始めて全ての辺を通りそこに戻ってくる一筆書きがある．つまり，全ての辺のコストの和が答え．

準オイラーグラフ

2 つの奇数次の頂点を v1, v2 とすると，v1から始めて全ての辺を通りv2に至るような一筆書きがある．つまり，（v1からv2へ至る一筆書き + v2からv1への最短経路）の総コストが答え．

オイラーグラフなら全ての頂点は偶数次だし，準オイラーグラフなら奇数次の頂点が二つ，という点で判定できる．

奇数次の頂点が1つということはない．これは，連結グラフだし，問題文で「ある頂点から出てそこにまた入る辺は存在しないし，任意の2頂点間を直接繋ぐ辺は高々一つ，任意の2頂点間を繋ぐパスが存在する」と言っている．直感的には，上の条件から，グラフに辺を一つ追加したら互いに異なる2つの頂点の次数がそれぞれ 1 増えるので，ある頂点が奇数次なら必ずもう一つ奇数次の頂点が存在する，という感じでしょうか．

書いたダイクストラ法がバグってて，数回 Wrong Answer 喰らってしまった．