Submission #6442064

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <queue>
#include <vector>
#include <iostream>
#include <tuple>
using namespace std;

void chmax(int &A, int B) { A = max(A, B); }

// 移動元と行先と辺のコストを記録する構造体
template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d = 1) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T = int>
using Graph = vector< vector< Edge<T> > >;

// 強連結成分分解
// Verified: AOJ GRL_3_C (Strongly Connected Components)
// Verified: ARC030 C (有向グラフ) ← 強連結を潰したグラフの構築の検証

// これは 2 回の DFS によって実現できる。
// はじめに普通の DFS をするが、その時に帰りがけ順に頂点番号の配列を作る。
// 次に、元のグラフの逆辺のみで構成されたグラフに対して、
// 帰りがけ順が遅かったものから順に DFS を行う。
// 帰りかけが遅かった頂点ほど、 DAG の先頭の強連結成分に属しているため、
// 辺を逆向きにすると、先頭の強連結成分から外に出られなくなることを利用している。

template <typename T = int>
struct GraphSCC {
public:
    const int n;
    vector<bool> isthrough;
    vector<int> vs, cmp;
    vector< vector<int> > G, rG, H; // グラフ、逆辺グラフ、縮約後のグラフ

    GraphSCC(vector< vector< Edge<T> > > &g) :
        n(g.size()), isthrough(n, false), cmp(n, 0), G(n), rG(n) {
        for(int i=0; i<n; i++) {
            for(size_t j=0; j<g[i].size(); j++) {
                G[i].push_back(g[i][j].to);
                rG[ g[i][j].to ].push_back(i);
            }
        }
    }

    void SCC_dfsone(int cur) {
        isthrough[cur] = true;
        for(size_t i=0; i<G[cur].size(); i++) {
            if(!isthrough[G[cur][i]]) {
                SCC_dfsone(G[cur][i]);
            }
        }
        vs.push_back(cur);
    }

    void SCC_dfstwo(vector<int> &vec, int cur, int k) {
        cmp[cur] = k;
        isthrough[cur] = true;
        vec.push_back(cur);
        for(size_t i=0; i<rG[cur].size(); i++) {
            if(!isthrough[rG[cur][i]]) {
                SCC_dfstwo(vec, rG[cur][i], k);
            }
        }
    }

    // 縮約後のグループ、グループ数
    pair<vector<int>, int> scc() {
        // 1回めのDFS
        for(int i=0; i<n; i++)
            if(!isthrough[i]) SCC_dfsone(i);

        fill(isthrough.begin(), isthrough.end(), false);
        reverse(vs.begin(), vs.end());
        int k = 0; vector< vector<int> > S;

        // 2回めのDFS
        for(size_t i=0; i<vs.size(); i++) {
            if(!isthrough[vs[i]]) {
                S.push_back(vector<int>());
                SCC_dfstwo(S.back(), vs[i], k++);
            }
        }

        H.resize(k);
        fill(isthrough.begin(), isthrough.end(), false);
        for(size_t i=0; i<k; i++) {
            for(size_t j=0; j<S[i].size(); j++) {
                int v = S[i][j];
                for(size_t x=0; x<G[v].size(); x++) {
                    int u = G[v][x];
                    if(isthrough[cmp[u]] || cmp[v] == cmp[u]) continue;
                    isthrough[cmp[u]] = true;
                    H[cmp[v]].push_back(cmp[u]);
                }
            }
            for(size_t j=0; j<H[i].size(); j++) isthrough[ H[i][j] ] = false;
        }
        return make_pair(cmp, k);
    }
};


int main() {
    int N; cin >> N;
    Graph<> G(N);
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            int v; cin >> v;
            if(v) G[i].emplace_back(j);
        }
    }

    GraphSCC<> sc(G);
    vector<int> cmp; int M;
    tie(cmp, M) = sc.scc();
    vector< vector<int> > adj(M+1, vector<int>(M+1));
    
    vector< vector<int> > F(M+1);
    vector<int> indeg(M+1);
    for(int i=0; i<M; i++) {
        F[M].emplace_back(i);
        indeg[i]++;
        adj[M][i] = true;
        for(auto to : sc.H[i]) {
            F[i].emplace_back(to);
            indeg[to]++;
            adj[i][to] = true;
        }
    }

    /*
    for(int i=0; i<=M; i++) {
        for(int j=0; j<=M; j++) {
            fprintf(stderr, "%d%c", adj[i][j], " \n"[j==M]);
        }
    }
    */

    vector<int> topo, weight(M+1);
    queue<int> que;
    for(int i=0; i<N; i++) {
        weight[ cmp[i] ]++;
    }
    for(int i=0; i<=M; i++) {
        if(indeg[i] == 0) {
            topo.emplace_back(i);
            que.emplace(i);
        }
    }

    while(que.size()) {
        int cur = que.front(); que.pop();
        for(auto to : F[cur]) {
            if(--indeg[to] == 0) {
                topo.emplace_back(to);
                que.emplace(to);
            }
        }
    }

    vector< vector<int> > dp(M+1, vector<int>(M+1));
    dp[0][0] = 0;
    for(int i=0; i<=M; i++) {
        for(int j=0; j<=M; j++) {
            int u = topo[i], v = topo[j];

            // i 側を進める
            for(int k=i+1; k<=M; k++) {
                int w = topo[k];
                if(adj[u][w]) chmax(dp[k][j], dp[i][j] + weight[w]);
            }

            // j 側を進める
            for(int k=i+1; k<=M; k++) {
                int w = topo[k];
                if(adj[u][w] or adj[v][w]) chmax(dp[k][i], dp[i][j] + weight[w]);
            }
        }
    }

    int ans = 0;
    for(int i=0; i<=M; i++) for(int j=0; j<=M; j++) {
            chmax(ans, dp[i][j]);
        }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result