POJ-3687: Labeling Balls

keyword

有向グラフ　トポロジカルソート　辞書順最小　C++

問題概要

ノード数N(<200)、辺の数M(<40000)の有向グラフが与えられる。このとき、グラフがDAGであるならば、ノードに辞書順最小のトポロジカル順序を与える問題。

解法

辞書順最小はGreedy。まず前処理として、DAGの判定も込めてWarshall-Floydしておく。ノード数の小さい順に次の処理をしていく。

• 下流にある未処理のノードの数だけ小さい番号を確保して置かなければならないので、自分には小さい方から数えて(下流にある個数+1)番目の番号を割り振る。
• 下流にある全てのノードに対して再帰的に同様の処理をする。

感想

辺を選ぶ順序を適切にすれば普通のトポロジカルソートと同じように帰りがけに番号振っていけばいいと思って大分ハマった。

POJ-3159: Candies

keyword

Dijkstra　C++

問題概要

ノード数V(<3*10^4)、辺の数E(<1.5*10^5)の重み付き有向グラフが与えられる。ある点からある点までの距離を求める問題。

解法

DijkstraするだけなんだけどTLEが異常に厳しいので細々とした高速化をして通った。Forum見てるとSPFAという方法があるらしく、ちょっと調べてみたけどBellman-Fordとの違いがよく分からなかった。priority_queueを使っていない分早くなるかもしれないということなんだろうか。