Typical DP Contest R - グラフ

問題

tdpc.contest.atcoder.jp

解法

まず強連結成分分解して, DAG の形にします(下のコードでは SCC ライブラリを使わないで Warshall-Floyd を使っていますが)。

そしたら, DAG のあるノードに訪れたとすると, そのノードに含まれる頂点数(強連結成分の数)分だけ頂点を訪れたと考えても良いです。ということで, 操作の回数が 1 回だったら, dp[u] = (今 DAG 上で頂点 u にいる時, 黒い頂点に塗ることの出来る最大値) という DP が結構簡単に出来ます。

操作の回数が 2 回だったらどうすれば良いかというと, dp[u][v] = (DAG 上で 1 つの頂点が u に, もうひとつの頂点が v にあるときに, 黒い頂点に塗ることの出来る最大値) とします。ただ, これだと u と v で進路がかぶり, ダブって黒く塗った判定をしてしまう可能性があるので, u の次に訪れることの出来る頂点 i は, u -> i と訪れることが出来, i -> v と訪れることの出来ない頂点, とします。こうするとダブって頂点を塗った判定をすることはないです。

2 回操作するなら状態に 2 頂点を持てばいいじゃない！というのは思いついたし大事な発想だと思うんですが, ダブらないようにするために訪れる頂点を限定する, というテクは思いつかなかったです。有用そうなので覚えておこう。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

const int MAXN = 333;
int g[MAXN][MAXN];
bool can[MAXN][MAXN], can2[MAXN][MAXN];
int dp[MAXN][MAXN], score[MAXN];

int dfs(int u, int v, const int size) {
    int& ret = dp[u][v];
    if (ret >= 0) return ret;
    ret = 0;
    // u を動かす
    for (int i = 0; i < size; i++) {
        if (u == i) continue;
        if (!can2[u][i] || can2[i][v]) continue;
        ret = max(ret, dfs(i, v, size) + score[i]);
    }
    // v を動かす
    for (int i = 0; i < size; i++) {
        if (v == i) continue;
        if (!can2[v][i] || can2[i][u]) continue;
        ret = max(ret, dfs(u, i, size) + score[i]);
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) can[i][i] = true;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> g[i][j];
            if (g[i][j]) can[i][j] = true;
        }
    }
    for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        can[i][j] |= can[i][k] & can[k][j];
    }
    UnionFind uf(N);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (can[i][j] && can[j][i]) uf.unite(i, j);
    }
    vector<vi> comp;
    map<int, int> trans;
    for (int i = 0; i < N; i++) trans[uf.find(i)] = 0;
    {
        int k = 0;
        for (auto& p : trans) p.second = k++;
        comp.resize(k);
    }
    for (int i = 0; i < N; i++) {
        int index = trans[uf.find(i)];
        comp[index].push_back(i);
        score[index] = uf.count(i);
    }
    int size = comp.size();
    vector<vi> G(size);
    for (int i = 0; i < size; i++) {
        set<int> S;
        for (int el : comp[i]) {
            for (int j = 0; j < N; j++) {
                if (g[el][j]) S.insert(trans[uf.find(j)]);
            }
        }
        for (int el : S) if (el != i) G[i].push_back(el);
    }
    for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) {
        if (can[comp[i][0]][comp[j][0]]) can2[i][j] = true;
    }
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) {
        ans = max(ans, dfs(i, j, size) + (i==j ? score[i] : score[i]+score[j]));
    }
    cout << ans << endl;
    return 0;
}