rt

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=100010;
int n,m,tu,tv;
int dfn[N],low[N],vis[N],cnt;
bool b[N];
int w[N],id[N],ans[N];
stack <int> s;
int h[N],e[M],ne[M],idx;
int h1[N],e1[M],ne1[M],idx1;
void addEdge1(int u,int v)
{
	e1[idx1]=v;
	ne1[idx1]=h1[u];
	h1[u]=idx1++;
}
void addEdge(int u,int v)
{
	e[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
}
void Tarjan(int u)
{
	dfn[u]=low[u]=++cnt;
	s.push(u);
	vis[u]=1;
	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(vis[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		int v;
		do{
			v=s.top();
			s.pop();
			vis[v]=0;
			if(v!=u) w[u]+=w[v],w[v]=0;
			id[v]=u;
		}while(v!=u);
	}
}
void dfs(int x)
{
	if(ans[x]>0) return;
	int maxn=0;
	for(int i=h1[x];~i;i=ne1[i])
	{
		if(ans[e1[i]]==0) dfs(e1[i]);
		maxn=max(ans[e1[i]],maxn);
//		cout << ans[e1[i]] << endl;
	}
	ans[x]=w[x]+maxn;
}
int main()
{
	memset(h,-1,sizeof h);
	memset(h1,-1,sizeof h1);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&tu,&tv);
		addEdge(tu,tv);
	}
	for(int i=1;i<=n;++i)
		if(dfn[i]==0)
			Tarjan(i);
	
	for(int i=1;i<=n;++i)
		for(int j=h[i];~j;j=ne[j])
		{
			int v = e[j];
			if(id[i]!=id[v])
				addEdge1(id[i],id[v]);
		}
			
	int maxn=-1;
	for(int i=1;i<=n;++i)
		if(!ans[id[i]])
		{
			dfs(id[i]);
			maxn=max(maxn,ans[id[i]]);
//			cout<<ans[i]<<endl;
		}
//	for(int i = 1;i <= n;i++) cout << w[i] << " ";
	printf("%d\n",maxn);
	return 0;
}