Typical DP Contest R - グラフ

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_graph

解法

どう考えても閉路は一つにまとめたいな～という気持ちになるので，とりあえずSCCしたあとのDAGの上で解くことを考えます．
一番端っこから引いていくのが当然良いので，トポロジカルソートしてその順番にDPしていくことを考えます．

2本引いていくため，以下のようなDPでうまく状態を持ちます．
dp[i][j] := 最後に伸ばした辺の先が i で，もう一方の端が j であるときの最大
このとき，j がトポロジカル順序で i を越えないようにもっておくことで，同じ頂点をカウントせずに済ませることができます．

遷移は，i から伸ばすか j から伸ばすかで2通りあります．（伸ばそうとする先は i よりトポロジカル順序があとの頂点．）
i から伸ばすのは自由なので普通に伸ばします．
j から伸ばすときは，重複カウントを避けるために i を飛び越えて伸ばさなければなりません．あらかじめ j から（いくつかの頂点を辿って）k にいけるかどうかを計算しておくと実現できます．

サイズ0のダミーの頂点をトポロジカル順序で一番最初にくるように入れておくと，一番最初の頂点を選ぶ操作をさっきの遷移で自然に実現できるので楽です．
この頂点は他のすべての頂点にいけるようにしておきます（逆は行けない）．

max(dp[i][j]) が答えになります．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using graph = std::vector<std::vector<int>>;

// SCC と tsort は略

int main() {
    int N;
    cin >> N;
    graph gg(N, vector<int>(N));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            cin >> gg[i][j];
        }
    }

    vector<int> cmp(N);
    int const K = scc(gg, cmp);
    auto g = build_graph(gg, cmp, K);
    vector<int> sz(K + 1);
    for(int i = 0; i < N; ++i) {
        sz[cmp[i]]++;
    }

    auto topo = tsort(g);         // トポロジカルソートする
    topo.insert(topo.begin(), K); // ダミーの頂点

    // いくつかの頂点と通って行けるかどうか
    vector<vector<bool>> can(K + 1, vector<bool>(K + 1));
    for(int i = 0; i < K; ++i) {
        can[K][i] = 1;
    }
    for(int i = 0; i < K; ++i) {
        for(int j = 0; j < K; ++j) {
            can[i][j] = g[i][j];
        }
    }
    for(int k = 0; k < K + 1; ++k) {
        for(int i = 0; i < K + 1; ++i) {
            for(int j = 0; j < K + 1; ++j) {
                can[i][j] = can[i][j] | can[i][k] & can[k][j];
            }
        }
    }

    vector<vector<int>> dp(K + 1, vector<int>(K + 1));
    for(int i = 0; i < K + 1; ++i) {
        for(int j = 0; j < i; ++j) {
            int u = topo[i], v = topo[j];
            dp[u][v] = max(dp[u][v], sz[u] + sz[v]);
            for(int k = i + 1; k < K + 1; ++k) {
                int w = topo[k];
                if(can[u][w]) {
                    dp[w][v] = max(dp[w][v], dp[u][v] + sz[w]);
                }
                if(can[v][w]) {
                    dp[w][u] = max(dp[w][u], dp[u][v] + sz[w]);
                }
            }
        }
    }

    int res = 0;
    for(int i = 0; i < K + 1; ++i) {
        for(int j = 0; j < K + 1; ++j) {
            res = max(res, dp[i][j]);
        }
    }

    cout << res << endl;
}

感想

SCCとかトポロジカル順序の発想は自然だし，遷移はかなりわかりやすいし，コードも別にややこしくないけど，DPテーブルの持ち方考えるのは結構つらいと思った．
これが簡単だと思える人はどんな訓練を積んできたんですかね……？