9/16 PKU

1041 John's trip

非常に簡略化して言うと、辺の番号を通る順番に並べたとき辞書順に最小になるオイラー閉路を求めよ、という問題。

オイラー閉路が存在することと「各頂点から出る辺の数が偶数で、すべての頂点が連結である」ことは同値である。まず、これで閉路の存在性を確かめる。
もし閉路が存在するなら、最小の番号を持つ辺の両端の頂点から、その頂点を出発点としたときに辞書順最小の閉路を求めることを考える。
各頂点では、できるだけ小さい番号の辺に進む。ここで、進めるための条件は、「進んだ先の頂点から他のすべての辺まで辿れる」ことである。このテストはすぐに行える。もしある辺に進めることがわかったら、その辺に進み、その頂点から同じことを辺がすべてなくなるまで繰り返す。
こうすると、最小番号辺の両端からそれぞれ探索を始めたので、2つ閉路の順序が求まる。このうち、辞書順でより小さいものを出力すればよい。

1511 Invitation Cards

有向グラフが与えられるので、「頂点1から他の頂点までの最短コストの和」＋「頂点1以外の頂点から頂点1までの最短コストの和」を求めよ。

頂点1からダイクストラやるだけ。入力が馬鹿でかいのでTLE対策でpriority_queueの代わりに一応本式の静的ヒープを書いた。

2230 Watchcow

無向グラフが与えられるので、頂点1で始まり、すべての辺を2方向に通過し、頂点1で終わるような経路を1つ出力せよ。

DFSやるだけ