40分求条必关

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m,h[N],e[M],ne[M],id;
int dfn[N],low[N],idx=0,st[N],ins[N],top=0,scc[N],cnt=0;
long long w[N],dp[N],sum=0,ans=LLONG_MIN;;
void add(int a,int b){
	id++;
	e[id]=b;
	ne[id]=h[a];
	h[a]=id;
}
void tarjan(int u){
	dfn[u]=++idx;
	low[u]=idx;
	ins[u]=1;
	st[++top]=u;
	for(int i=h[u];i;i=ne[i]){
		int v=e[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]); 
		}
		else if(ins[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		++cnt;
		while(1){
			int v=st[top--];
			ins[v]=0;
			scc[v]=cnt;
			sum+=w[v];
			for(int i=h[v];i;i=ne[i]){
				dp[cnt]=max(dp[cnt],dp[scc[e[i]]]);
			}
			if(v==u)break;
		}
		dp[cnt]+=sum;
		ans=max(ans,dp[cnt]);
	}
}
int main(){
	cin>>n>>m;
	memset(h,0,sizeof(h));
	for(int i=1;i<=n;i++){
		cin>>w[i];
	} 
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	cout<<ans<<endl;
	return 0;
}