【No.028】「ICPC2016 つくば大会 H問題 Animal Companion Maze」
・簡単な問題概要
AIZU ONLINE JUDGE ←問題文へのリンク
n個のノードと、m個のエッジで構成されたグラフが入力で与えられます。
ただし、エッジには双方向のエッジと単方向のエッジの2種類があります。
そのグラフに閉路があるならば"Infinite"を出力してください。
閉路がないならば、そのグラフで作ることのできるパスの中で最長のものを見つけ、その長さを出力してください。
※自己ループは存在しないが、多重辺は存在し得る。
2≦n≦100000 , 1≦m≦100000
自分が考えた解法
Infiniteの判定パート と 最長のパスを見つけるパート の2つに分けます。
まず、双方向のエッジのみで閉路が作れるかどうかを判定します。
これはグラフから単方向のエッジをすべて削除したとき、グラフが森になっているかどうかと同じです。
今度は単方向のエッジが使われている閉路が存在するかどうかを判定します。
これは双方向のエッジのみで互いに行き来できるノードどうしを併合して縮約することによりできるグラフがDAGになっているかどうかを判定することでできます。
( 今回僕はDAGになっているかどうかの判定を行うためにトポロジカルソートを行いました。なぜかというと、この時に得たトポロジカル順序が最長のパスを見つけるDPの役に立つからです。 )
これで"Infinitite"と出力しなければならないかの判定は終了で、あとは最長のパスを見つけるパートです。
dp[ i ] = 適当なノードから始まり、i 番目のノードで終了しているパスの中で最長の長さ
と定義します。( このDP配列はすべて0で初期化しておきます。)
先ほどのDAGかどうかの判定をするときに得たトポロジカル順に、「双方向のエッジのみで行き来できるノードどうしを併合したグループ」を1つ1つ見ていきます。
あるグループを見るごとに、そのグループに含まれているノード1つ1つに対応したDP配列の要素たちを埋めて行きます。
今見ているグループの中に単方向のエッジが入ってこない場合(グループの入次数が0の場合)は、木の直径を求めることで簡単にDP配列を埋めることができます。
dp[ i ] の値は、木の直経の両端のノードのうち、どちらか一方からスタートして、 i 番目のノードに行くときのエッジの本数の最大値になります。
(どのグループも、双方向のエッジのみに着目すれば木となっていることが重要です。)
今見ているグループの中に単方向のエッジが入ってきている場合でも、そのエッジの数だけ、グラフに新しいノードと重みつきのエッジを追加することで先ほどと同じようにDP配列を埋めることができます。( 図があるとわかりやすいので、スライドを作りました。そちらを参照してください。)
一応、自分が書いたソースコードを置いておきます。
いろいろ工夫していて多少解説の内容と異なっているところがあります。
ご了承ください。
gistddff253ccf74c40aa3045bb087e53d6e
とても難しくて、とても面白い問題だったので気合を入れて解説を書きました。
