RT

Code：

#include<iostream>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
int dfn[10005],low[10005],vis[10005],tot,gx,in[10005],x[100005],y[100005],dis[10005],scp[10005],c[10005],id[10005],gs[10005];
stack<int> s;
vector<int> G[10005],T[10005];
queue<int> q;
void tarjan(int x){
	s.push(x);
	dfn[x]=low[x]=++tot;vis[x]=1;
	for(int i=0;i<G[x].size();i++){
		if(!dfn[G[x][i]]){
			tarjan(G[x][i]);
			low[x]=min(low[x],low[G[x][i]]);
		}
		else if(vis[G[x][i]]){
			low[x]=min(low[x],low[G[x][i]]);
		}
	}
	int k;
    if(low[x]==dfn[x]){
    	while(!s.empty()){
    		k=s.top();
            s.pop();
            vis[k]=0;
            scp[k]=x;
            if(k==x){
            	break;
			}
            dis[x]+=dis[k];
        }
    }
}
int main(){
	int n,m,ans=0,ix=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>dis[i];
	}
	while(m--){
		cin>>x[ix]>>y[ix];
		G[x[ix]].push_back(y[ix]);
		ix++;
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=m;i++){
		if(scp[x[i]]==scp[y[i]]){
			continue;
		}
		T[scp[x[i]]].push_back(scp[y[i]]);
		in[scp[y[i]]]++;
	}
	for(int i=1;i<=n;i++){
		if(scp[i]==i&&!in[i]){
			c[i]=dis[i];
			q.push(i); 
		}
	}
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		for(int i=0;i<T[cur].size();i++){
			in[T[cur][i]]--;
			c[T[cur][i]]=max(c[cur]+dis[T[cur][i]],c[T[cur][i]]);
			if(!in[T[cur][i]]){
				q.push(T[cur][i]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<c[i]<<endl;
		ans=max(ans,c[i]);
	}
	cout<<ans;
	return 0;
}