Typical DP Contest R - グラフ

問題

有効グラフをたどって訪れることができるノードの最大数を求める。 この操作は2回行えるが、重複したノードは一度しか数えない。

考察

強連結成分分解を行い、相互に行き来可能なノードの塊を一つのノードとみなしたDAGを考える。 DAGの各ノードのスコアを強連結成分内の元のノードの数として、DAG上でスコア付きでこの問題を解くようにする。

つぎのようなDPを考える。

1回目に頂点、2回目に頂点から操作を始めたときの最大スコア

とする。から遷移を始めるとき、が可能で、が不可能なノードだけに限定する。これで、カウントの重複を防げる。

実装

atcoder.jp

感想

頂点の直接の子でなくても到達可能なら一気に飛ばすのも、そもそも訪れる頂点を制限する発想は面白い。