ARC#030 C.有向グラフ

その他 過去問

問題

n頂点の有向グラフが与えられ、各頂点にはアルファベット1文字が書かれている。
任意頂点から進んで、アルファベットを順番に回収して長さkの文字列を作る。
頂点にたどり着いたとき、アルファベットを回収してもしなくてもよい。
このとき、可能な辞書順最小の文字列を求める。なければ-1を出力。

k<=n<=300
辺数<=300

考え方

解説：http://www.slideshare.net/chokudai/arc030


何度も同じ頂点を通れたり、回収しなくてもよかったりするため、どこのアルファベットを回収してきたか？を保持する方法だと間に合わない。
「辞書順最小」なので最小となるものから選んでいくような方法を考えてみるも、適用は難しい。


なんとか一度通ったところは再び計算しなくて済むようにしたい。
強連結成分分解を行い、強連結成分部分を一つのノードと考えると、グラフをDAGと見なせる。
DAGであれば、各強連結成分ごと順番にDPすれば、k文字で辞書順最小の文字列を求めることができる。
各強連結成分内で作れる文字列は、任意の順番に任意文字を使って作れるので、文字をソートして小さいアルファベットから何文字かとることを考えればよい。


dp[強連結成分i][文字数k] := 強連結成分iまでを使って、文字長kで辞書順最小の文字列

DAGでのdpなので、各強連結成分について、そこにつながる一つ前の強連結成分からもらうdpを考えればよい。
dp[一つ前の強連結成分j][文字数l]に、強連結成分iの何文字かを足して長さkになるもので辞書順最小の文字列をdpに保持する。

計算量は、強連結成分分解がO(n+m)で、dpが大雑把にO(強連結成分数n*強連結成分内の文字数k*一つ前の強連結成分n?*文字列比較k)=O((nk)^2)ぐらいで怪しいが、実際は、文字列比較がそこまで大きくならないのと、成分内の文字数kやひとつ前の成分の数もそこまで大きくならないので、余裕で間に合う模様。

反省

dpの初期値として空文字にして、結果がなかった場合もから文字としてしまって、処理したかどうかを区別できなくなって何度も計算しに行ってTLEしてた。


強連結成分を見つけるところはワーシャルフロイドなどで、頂点iから頂点jに行けるか？(推移性)を計算して出してもOK(ただしO(N^3))。


他の人の解法見てみると、ret="~"とかret="}"とかを入れておいて、ret=min(ret,文字列)でやってみるみたい。
(~はasciiコードで126なので、どのアルファベットよりも大きい番号)



その他

http://www.prefield.com/algorithm/graph/strongly_connected_components.html
dfs1回で求める方法があるっぽい。