玄关
查看原帖
玄关
1046406
Unpt_V3楼主2024/7/13 17:52
#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;
int n, m, s, e, f[N];
long long dfn[N], low[N], belong[N], sz[N], in[N], dis[N], ind, tot;
vector<int> p[N], g[N];  // g是缩点后的图
stack<int> st;
queue<int> q;
bool vis[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++ind;
    vis[u] = true;
    st.push(u);
    for (auto v : p[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        tot++;
        while (st.top() != u) {
            int v = st.top();
            vis[v] = false;
            st.pop();
            belong[v] = tot;
            sz[tot] += f[v];
        }
        vis[u] = false;
        st.pop();
        belong[u] = tot;
        sz[tot] += f[u];
    }
}

long long topo() {
    int x = belong[s], y = belong[e];
    q.push(x);
    dis[x] = sz[x];
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = true;
        for (auto v : g[u]) {
            if (!vis[v])
                dis[v] = max(dis[v], dis[u] + sz[v]);
            else dis[v] = max(dis[v], dis[u]);
            in[v]--;
            if (!in[v])
                q.push(v);
        }
    }
    return dis[y];
}

int main() {
    cin >> n >> m >> s >> e;
    for (int i = 1; i <= n; i++)
        cin >> f[i];
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        p[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int x = 1; x <= n; x++) {
        for (auto y : p[x]) {
            int v = belong[y], u = belong[x];
            if (u != v) {
                g[u].push_back(v);
                in[v]++;
            }
        }
    }
    memset(vis, false, sizeof(vis));
    cout << topo() << endl;
    return 0;
}
2024/7/13 17:52
加载中...