40分求条必关

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m;
int ind,low[N],dfn[N];
int scc_cnt,scc[N],ins[N];
int cnt=0,in[N],dp[N],a[N],na[N];
stack<int>s;
vector<int>ans[N];
struct graph{
	int tot,hd[N];
	int nxt[M],to[M];
	void add(int x,int y){
		tot++;
		nxt[tot]=hd[x];
		hd[x]=tot;
		to[tot]=y;
	}
}g,gg;
void Tarjan(int u){
	dfn[u]=low[u]=++ind;
	s.push(u);
	ins[u]=1;
	for(int i=g.hd[u];i;i=g.nxt[i]){
		if(!dfn[g.to[i]]){
			Tarjan(g.to[i]);
			low[u]=min(low[u],low[g.to[i]]);
		}
		else if(ins[g.to[i]])low[u]=min(low[u],dfn[g.to[i]]);
	}	
	if(dfn[u]==low[u]){
		scc[u]=++scc_cnt;
		while(s.top()!=u){
			scc[s.top()]=scc_cnt;
			ins[s.top()]=0;
			s.pop();
		}
	}
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		g.add(a,b);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	for(int i=1;i<=n;i++){
		na[scc[i]]+=a[i];
		for(int j=g.hd[i];j;j=g.nxt[j]){
			int u=scc[i],v=scc[g.to[j]];
			if(v!=u){
				gg.add(u,v);
				in[v]++;
			}
		}
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
			dp[i]=na[i];
		}
	}
	int res=INT_MIN;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		res=max(res,dp[u]);
		for(int v=gg.hd[u];v;v=gg.nxt[v]){
			dp[v]=max(dp[v],dp[u]+na[v]); 
			in[v]--;
			if(in[v]==0){
				q.push(v);
			}
		}
	}
	cout<<res;
	return 0;
}