https://www.luogu.com.cn/record/109427031

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef int lsqxx;
struct lq{
    lsqxx v,nxt,w;
}e[200005],g[200005];
lsqxx h[20005],cnt,gh[20005],gcnt;
void add(lsqxx u,lsqxx v)
{
    e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;
}
void addg(lsqxx u,lsqxx v,lsqxx w)
{
	g[++gcnt].v=v;g[gcnt].nxt=gh[u];gh[u]=gcnt;g[gcnt].w=w;
}
int n,m;
int x,y;
int dfn[20005],low[20005],refn[20005];
int vis[20005],dis[20005];
int dfnx;
void tarjan(int t)
{
    dis[t]=1;
    vis[t]=1;
    if(!dfn[t])
        dfn[t]=low[t]=++dfnx,refn[dfnx]=t;
    for(int i=h[t];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(vis[v])
        {
            if(dis[v])
                low[t]=min(low[t],low[v]);
        }
        else
        {
            tarjan(v);
            low[t]=min(low[t],low[v]);
        }
    }
    dis[t]=0;
}
int cnts[20005],ans;
int getfa(int x)//传入结点，传出dfn序 
{
	if(low[x]==dfn[x]) return low[x];
	return low[x]=getfa(refn[low[x]]);
}
int vcnt;
int a[20005],b[20005],d[20005];
queue<int>q;
void TP()
{
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=gh[u];i;i=g[i].nxt)
		{
			int v=g[i].v,w=g[i].w;
			d[v]--;
			b[v]=max(b[v],b[u]+w);
			if(!d[v])
				q.push(v);
		}
	}
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&x,&y),add(x,y);
    for(int i=1;i<=n;i++)
        if(!vis[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
    	getfa(i);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
    	if(low[i]==dfn[i])
    		if(vis[i])
    			b[vis[i]]+=a[i];
    		else
    			vis[i]=++vcnt,
    			b[vis[i]]+=a[i];
    	else
    		if(vis[refn[low[i]]])
    			b[vis[refn[low[i]]]]+=a[i];
    		else
    			vis[refn[low[i]]]=++vcnt,
    			b[vis[refn[low[i]]]]+=a[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=h[i];j;j=e[j].nxt)
		{
			int v=e[j].v;
			if(low[i]==low[v]) continue;
			addg(vis[refn[low[i]]],vis[refn[low[v]]],b[vis[refn[low[v]]]]);
			d[vis[refn[low[v]]]]++;
		}
	for(int i=1;i<=vcnt;i++)
		if(!d[i]) q.push(i);
	TP();
	int ans=0;
	for(int i=1;i<=vcnt;i++)
		ans=max(ans,b[i]);
	cout<<ans;
    return 0;
}