如题

#include<bits/stdc++.h>
using namespace std;
int n,m,tot,head[10010],val[10010],ntot,nhead[10010],nval[10010];
int dfn[10010],low[10010],belong[10010],cnt,idx;
int in[10010],dp[10010];
bool ins[10010];
struct node
{
	int u,v,nxt;
}e[100010],ne[100010];
stack<int>S;
void add(int u,int v)
{
	tot++;
	e[tot].u=u;
	e[tot].v=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void nadd(int u,int v)
{
	ntot++;
	ne[ntot].u=u;
	ne[ntot].v=v;
	ne[ntot].nxt=nhead[u];
	nhead[u]=ntot;
	in[v]++;
}
void tarjan(int u)
{
	int v;
	dfn[u]=low[u]=++idx;
	S.push(u);
	ins[u]=1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		v=e[i].v;
		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++;
		do
		{
			v=S.top();
			S.pop();
			ins[v]=0;
			belong[v]=cnt;
			nval[cnt]+=val[v];
		}while(u!=v);
	}
}
int calc()
{
	queue<int>q;
	int ans=0;
	for(int i=1;i<=cnt;i++)
	{
		if(!in[i])
		{
			q.push(i);
			dp[i]=nval[i];
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=nhead[u];i;i=ne[i].nxt)
		{
			int v=ne[i].v;
			in[v]--;
			dp[v]=max(dp[v],dp[u]+nval[v]);
			if(!in[v])q.push(v);
		}
	}
	for(int i=1;i<=cnt;i++)ans=max(ans,dp[i]);
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&val[i]);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!belong[i])
		{
			idx=0;
			memset(dfn,0,sizeof(dfn));
			memset(low,0,sizeof(low));
			memset(ins,0,sizeof(ins));
			tarjan(i);
			while(!S.empty())S.pop();
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=e[j].nxt)
		{
			if(belong[i]!=belong[e[j].v])
				nadd(belong[i],belong[e[j].v]);
		}
	}
	printf("%d",calc());
	return 0;
}