Typical DP Contest - R グラフ

強連結成分分解とtopological sort が面倒だった。
dp[i][j] を最大にする path2 の経路の保存が必要か?と思いきやそんなこともなかったというのがミソなんだと思った。
class r_graph {
public:
    SCC scc_;
    //
    // 二つのパスの重なり部分は得点が加算されない。
    // この重なりはどうやって考えたらよいか？
    //
    void solve(void) {

            int N;
            cin>>N;
            scc_.init(N);

            // まず強連結成分分解をして DAG にする
            REP(i, N)
            {
                int has_edge;
                REP(j, N)
                {
                    cin>>has_edge;
                    if (has_edge) scc_.add(i,j);
                }
            }
            // 強連結成分分解
            int K = scc_.decompose();
            auto cmp = scc_.components();
            const auto &G = scc_.G_; // scc で入力にしたグラフを再利用

            // グラフを再構築
            // 強連結成分を重みをつけたグラフに縮約して DAG にする
            //
            //    * -> *
            //    ^    v
            // -> * <- *    =>  -> [4]
            //    |                 |
            //    +->...            +->...
            //
            vector<int> score(K, 0); // 重み
            REP(i, N)
                ++score[cmp[i]];

            vector<vector<int>> reduced(K);
            vector<vector<bool>> move(K, vector<bool>(K,false)); // rel[i][j] := i -> j へ移動できるか？
            // まず隣接する場所にだけフラグを建てる
            REP(i,N)
            for (auto j : G[i])
                move[cmp[i]][cmp[j]] = true;

            // 縮約グラフ作成
            REP(i, K)
            REP(j, K)
                if (move[i][j] && i != j) // 自分自身へのループはなし
                    reduced[i].push_back(j);

            // i -> j の移動が可能かの判定用に補完する
            REP(k, K)
                move[k][k] = true;

            REP(k, K)
            REP(i, K)
            REP(j, K)
                move[i][j] = move[i][j] || (move[i][k] && move[k][j]);

            // topological sort して根から DP する。
            vector<int> ord = topological_sort(reduced);

            //
            //  * 二本のパスはともに DAG の根からスタートさせる
            //
            //  0 -> 1 -> 2   3 -> 4 -> 5 -> ...
            //       |             ^
            //       +-------------+
            //
            // のように途中でパスの始点が変わる(0 or 3)ほうが得点が大きくなることも
            // ありうるが根(0)からスタートさせれば全てのケースを見れる。
            //
            // dp[i][j] := path1 の先頭が i で、path2 の先頭が j のときの最大スコア
            //             (i,j は topological_sort での順番)
            //
            // とし、この DP の更新を考える。
            //
            // i のノードが i1,i2,...,k,... に分岐しているとき
            //
            // A) k が j の先祖でなければそのま更新
            //  dp[k][j] = dp[i][j] + score[k]
            //
            // B) k が j の先祖なら
            //  1) dp[i][j] を最大にする path2 の経路上に k があるとき
            //  2) dp[i][j] を最大にする path2 の経路上に k がないとき(別経路がある)
            //
            // 1) ならすでに色がぬられているので dp[k][j] = dp[i][j]
            // 2) ならそのまま伸ばせるので A) と同じ
            //
            // => この判定のために dp[i][j] を最大にする path2 の経路の保存が必要か？
            //
            // 実は必要ない。
            // B) が起こる状況ではトポロジカルソートの順で k <= j となっている。
            //  よって 2) のケースは i,j を逆にしたときに計算されている
            //  1)の場合、 dp[k][j] = dp[i][j] そのもの。
            //
            vector<vector<int>> dp(K, vector<int>(K,0));
            vector<int> rord(K,0);
            REP(i, K)
                rord[ord[i]] = i;

            REP(i, K)
            REP(j, K)
            {
                //
                //     ki          kj
                //      \         /
                // ki'-- i - - - j - kj'
                //

                // まず i-j 間を評価
                if (i != j)
                    dp[i][j] = max(dp[i][j], score[ord[i]] + score[ord[j]]);
                else
                    dp[i][i] = max(dp[i][i], score[ord[i]]);

                int ni = ord[i];
                int nj = ord[j];
                // i から先を更新
                for(auto ki : reduced[ni])
                {
                    int k = rord[ki];
                    assert(k>i);  // topological sort 済みなので順序が保たれている
                    if (move[ki][nj]) // j-i-k が連結のとき
                        dp[k][j] = max(dp[k][j], dp[i][j]);
                    else
                        dp[k][j] = max(dp[k][j], dp[i][j] + score[ki]);
                }
                // j から先を更新
                for(auto kj : reduced[nj])
                {
                    int k = rord[kj];
                    assert(k>j);
                    if (move[kj][ni])
                        dp[i][k] = max(dp[i][k], dp[i][j]);
                    else
                        dp[i][k] = max(dp[i][k], dp[i][j] + score[kj]);
                }
            }
            int ret = 0;
            REP(i,K)
            REP(j,K)
                ret = max(ret, dp[i][j]);

            cout<<ret<<endl;
    }
};