Animal Companion in Maze (AOJ 1374)

$n$ 頂点 $m$ 辺のグラフが与えられる。

辺は無向と有向が混在していて、長さは全て $1$ である。

同じ辺を連続で通ってはいけないという制限のもと、最長 walk の長さを求めよ。

始点と終点は自由に選択して良い。

いくらでも長くできる場合は Infinite を出力。

$2 \le n \le 100000$

$1 \le m \le 100000$

多重辺が存在することはあるが、自己ループは存在しない。

無向辺だけみたときに無向閉路があれば Infinite

そうでなければ、無向辺部分は森である。

以後、無向辺だけみたときの連結成分をそれぞれ 1 つの頂点に潰した場合のグラフを考える。

有向辺が自己ループ or 有向閉路をもてば Infinite

そうでなければ答えは有限であり、DAG になっている。

あとは、トポロジカルソートしておいて、DAG 上での最長経路を求める dp をしながら、各頂点をみるタイミングで潰れた無向辺部分に再度注目して木の直径を求める全方位木 dp と同じようなことを行って更新すれば良い。

実装例

900点もなさそうだけど、初期重みがあるときの全方位木 dp のやり方や、どうやって最長経路 dp + 全方位木 dp で更新していくかで意外と苦戦した(潰す前のグラフでやるとトポソで変な頂点を先に見てしまうことがある)。

あああああ