【信息学做题日记】费了牛劲，终于AC掉缩点

// 题目: 【模板】缩点
// 链接: https://www.luogu.com.cn/problem/P3387
// 难度: 普及+/提高
#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

const int maxn = 1e4 + 10;
typedef long long ll;
int dfn[maxn], low[maxn], w[maxn], cnt[maxn], degree[maxn], dis[maxn], t = 1, n, m;
stack<int> st;
bool vis[maxn];

struct edge {
    int from, to, next;
} g[maxn * 11], g2[maxn * 11];
int head[maxn], head2[maxn];
int k = 0;

void add(int u, int v) {
    g[++k].to = v;
    g[k].from = u;
    g[k].next = head[u];
    head[u] = k;
}

void add2(int u, int v) {
    g2[++k].to = v;
    g2[k].from = u;
    g2[k].next = head2[u];
    head2[u] = k;
}

void tarjan(int x) {
    st.push(x);
    vis[x] = true;
    dfn[x] = t;
    low[x] = t;
    ++t;
    for (int i = head[x]; i; i = g[i].next) {
        int v = g[i].to;
        if (dfn[v] == 0) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if (vis[v]) {
            low[x] = min(low[x], low[v]);
        }
    }
    if (dfn[x] == low[x]) {
        while (!st.empty()) {
            int u = st.top();
            vis[u] = false;
            st.pop();
            cnt[u] = x;
            if (x == u) {
                break;
            }
            w[x] += w[u];
        }
    }
}

int topo() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (cnt[i] == i && !degree[i]) {
            q.push(i);
            dis[i] = w[i];
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head2[u]; i; i = g2[i].next) {
            int v = g2[i].to;
            dis[v] = max(dis[v], dis[u] + w[v]);
            --degree[v];
            if (!degree[v]) {
                q.push(v);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dis[i]);
    }
    return ans;
}


void best_coder() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    k = 0;
    for (int i = 1; i <= m; ++i) {
        if (cnt[g[i].from] != cnt[g[i].to]) {
            add2(cnt[g[i].from], cnt[g[i].to]);
            ++degree[cnt[g[i].to]];
        }
    }
    int ans = topo();
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}