请求加强数据
查看原帖
请求加强数据
681229
Your_Name楼主2024/10/15 16:28

这是我的代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
vector<int> G[N], H[N];
int ans, f[N], n, m, dfn[N], low[N], qlt[N], idx, vis[N], num, val[N], w[N], in[N];
stack<int> st;
void tarjan(int x){
    st.push(x);
    low[x] = dfn[x] = ++ idx;
    vis[x] = 1;
    for(auto i : G[x]){
        if(!dfn[i]){
            tarjan(i);
            low[x] = min(low[x], low[i]);
        }else if(vis[i]){
            low[x] = min(low[x], dfn[i]);
        }
    }
    if(low[x] == dfn[x]){
        num ++;
        int v;
        do{
            v = st.top();
            st.pop();
            qlt[v] = num;
            val[num] += w[v];
            vis[v] = 0;
        }while(x != v);
    }
}
void topo(){
    queue<int> q;
    for(int i = 1; i <= num; i ++){
        if(in[i] == 0){
            q.push(i);
            f[i] = val[i];
        }
    }
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        for(auto i : H[x]){
            f[i] = f[x] + val[i];//<-----这里
            in[i] --;
            if(in[i] == 0){
                q.push(i);
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
    }
    while(m --){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    for(int i = 1; i <= n; i ++){
        if(!dfn[i])tarjan(i);
    }
    for(int i = 1; i <= n; i ++){
        for(auto j : G[i]){
            if(qlt[i] == qlt[j])continue;
            H[qlt[i]].push_back(qlt[j]);
            in[qlt[j]] ++;
        }
    }
    topo();
    for(int i = 1; i <= num; i ++){
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}

可以看到我指的那个地方没写 max\max 但他也过了。

2024/10/15 16:28
加载中...