Submission #304526

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <complex>
#include <set>
#include <vector>
#include <stack>
#include <tuple>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <queue>

using namespace std;
typedef long long ll;
const int MN = 330;

template<int V>
struct SCC {
    vector<int> g[V], rg[V];
    void add(int i, int j) {
        g[i].push_back(j);
        rg[j].push_back(i);
    }

    vector<int> vs;
    bool used[V];
    void dfs(int v) {
        used[v] = true;
        for (int d: g[v]) {
            if (used[d]) continue;
            dfs(d);
        }
        vs.push_back(v);
    }
    int k;
    int res[V];
    vector<int> scc[V];
    void rdfs(int v) {
        used[v] = true;
        res[v] = k;
        scc[k].push_back(v);
        for (int d: rg[v]) {
            if (used[d]) continue;
            rdfs(d);
        }
    }

    int exec(int v) {
        fill_n(used, v, false);
        for (int i = 0; i < v; i++) {
            if (used[i]) continue;
            dfs(i);
        }
        fill_n(used, v, false);
        k = 0;
        for (int i = vs.size()-1; i >= 0; i--) {
            if (used[vs[i]]) continue;
            rdfs(vs[i]);
            k++;
        }
        return k;
    }
};

template<int V>
struct MinCostFlow {
    using T = int;
    using P = pair<T, int>;
    const T INF = 1<<28;
    struct Edge {
        int to, rev;
        int cap;
        T cost;
    };
    vector<Edge> g[V];
    T h[V], dist[V];
    int pv[V], pe[V];
    void add(int from, int to, int cap, T cost) {
        g[from].push_back(Edge{to, (int)g[to].size(), cap, cost});
        g[to].push_back(Edge{from, (int)g[from].size()-1, 0, -cost});
    }

    T exec(int s, int t, int f, bool bell = false) {
        T res = 0;
        fill_n(h, V, 0);
        while (f > 0) {
            fill_n(dist, V, INF);
            dist[s] = 0;
            if (bell) {
                bell = false;
                bool update;
                do {
                    update = false;
                    for (int v = 0; v < V; v++) {
                        if (dist[v] == INF) continue;
                        for (int i = 0; i < g[v].size(); i++) {
                            Edge &e = g[v][i];
                            if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                                dist[e.to] = dist[v] + e.cost;
                                pv[e.to] = v;
                                pe[e.to] = i;
                                update = true;
                            }
                        }
                    }
                } while (update);
            } else {
                priority_queue<P, vector<P>, greater<P>> que;
                que.push(P(0, s));
                while (!que.empty()) {
                    P p = que.top(); que.pop();
                    int v = p.second;
                    if (dist[v] < p.first) continue;
                    for (int i = 0; i < g[v].size(); i++) {
                        Edge &e = g[v][i];
                        if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                            dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                            pv[e.to] = v;
                            pe[e.to] = i;
                            que.push(P(dist[e.to], e.to));
                        }
                    }
                }
            }
            if (dist[t] == INF) {
                return -1;
            }
            for (int v = 0; v < V; v++) {
                h[v] += dist[v];
            }

            T d = f;
            for (int v = t; v != s; v = pv[v]) {
                d = min(d, g[pv[v]][pe[v]].cap);
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = pv[v]) {
                Edge &e = g[pv[v]][pe[v]];
                e.cap -= d;
                g[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

SCC<MN> scc;
MinCostFlow<MN*2> mf;
int u[MN][MN];
int g[MN][MN];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> u[i][j];
            if (!u[i][j]) continue;
            scc.add(i, j);
        }
    }
    int vs = scc.exec(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!u[i][j]) continue;
            g[scc.res[i]][scc.res[j]] = 1;
        }
    }
    n = vs;
    vs *= 2;
    int vt = vs+1;
    for (int i = 0; i < n; i++) {
        mf.add(i*2, i*2+1, 1, 0);
        mf.add(i*2, i*2+1, 1, -scc.scc[i].size());
        mf.add(vs, i*2, 2, 0);
        mf.add(i*2+1, vt, 2, 0);
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (!g[i][j]) continue;
            mf.add(i*2+1, j*2, 2, 0);
        }
    }
    cout << -mf.exec(vs, vt, 2, true) << endl;
    return 0;
}

Submission Info

Judge Result