Algoogle

Algorithm for Programming Contest

Typical DP Contest R - グラフ

Category: TDPC Tag: dp, strongly-connected-component, topological-sort

R - グラフ

問題概要


解法


まずsccして閉路を潰して,DAGをつくる(潰した閉路の頂点数を重さとする新しい頂点を作る).
その上でトポロジカルソートしたものを考える.

2本の辺の先端をみるDPをする.
dp[i][j] := 進んでる方の先端の位置がiでもう片方の先端の位置がjのときのそれまでに通った頂点数の最大値

また進む先はそこから到達可能ならどこでもよいが,現在のiより先に進むようにする.
これはiまでの頂点はすでに通った頂点かもしれないため.

また進んだ先の頂点の重さだけ現在の値に足す.
これも途中の頂点にすでに通った頂点があるかもしれないから.きちんと順に更新していけば結果は正しくなる.

コード


(R.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

inline void chmax(int &x, int y) { x = max(x, y); }

int n, m, id[310], w[310], done[310], dp[310][310], h[310][310];
vector<int> g[310], rg[310], f[310], scc[310], vs;

void dfs(int v) {
    if(done[v]) return;
    done[v] = 1;
    rep(i,g[v].size()) dfs(g[v][i]);
    vs.push_back(v);
}

void dfs2(int v) {
    if(!done[v]) return;
    done[v] = 0;
    id[v] = m;
    scc[m].push_back(v);
    rep(i,rg[v].size()) dfs2(rg[v][i]);
}

void topo(int v) {
    if(done[v]) return;
    done[v] = 1;
    rep(i,f[v].size()) topo(f[v][i]);
    vs.push_back(v);
}

int solve() {
    rep(i,n) dfs(i);
    m = 1;
    rep(i,n) if(done[vs[n-i-1]]) { dfs2(vs[n-i-1]); m++; }

    rep(i,m) {
        w[i] = scc[i].size();
        rep(j,w[i]) for(int &v: g[scc[i][j]]) f[i].push_back(id[v]);
        sort(begin(f[i]),end(f[i]));
        f[i].erase(unique(begin(f[i]),end(f[i])),end(f[i]));
    }
    rep(i,m-1) f[0].push_back(i+1);
    rep(i,m) rep(j,f[i].size()) h[i][f[i][j]] = 1;
    rep(k,m) rep(i,m) rep(j,m) h[i][j] |= h[i][k]&h[k][j];

    memset(done,0,sizeof(done));
    vs.clear();
    rep(i,m) topo(i);
    reverse(begin(vs),end(vs));

    rep(i,m) rep(j,i) {
        int u = vs[i], v = vs[j];
        chmax(dp[u][v], w[u]+w[v]);
        repi(k,i+1,m) {
            int nu = vs[k];
            if(h[u][nu]) chmax(dp[nu][v], dp[u][v]+w[nu]);
            if(h[v][nu]) chmax(dp[nu][u], dp[u][v]+w[nu]);
        }
    }
    int ans = 0;
    rep(i,m) rep(j,m) ans = max(ans, dp[i][j]);
    return ans;
}

void input() {
    cin >> n;
    int x;
    rep(i,n) rep(j,n) {
        cin >> x;
        if(x) {
            g[i].push_back(j);
            rg[j].push_back(i);
        }
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    input();
    cout << solve() << endl;
    return 0;
}

Comments