题目链接

思路

对于一个强连通分量，最优解是把上面的所有点都走一遍，因为不存在负权点。所以可以通过缩点统计每个强连通分量的权值之和。
记anss[u]为以节点u为终点的路径的最大权值。通过拓扑排序，对于任意入度为0的节点u，anss[u]已知，因为不存在其他能够到达u的点可以更新答案。入度不为0的点u，对于一条边(u->v)，易得anss[v]=MAX(anss[u]+a[v])。最终anss数组中的最大值即为答案。

Tarjan缩点算法

在有向图中，一些点两两之间可达，就可以把它们缩为一个点，进而将有向带环图转化为DAG求解。
Tarjan缩点算法通过dfs实现，将一个强连通分量中最早被访问到的点（即dfs序最小的点）作为该强连通分量的根节点。
为了记录每个节点被访问的时间，记录dfsn[i]为第i个节点的dfs序。low[i]为第i个节点在栈中能追溯到的最小的dfs序。若dfsn[i]==low[i]，那么i就是某个强连通分量的根节点。
定义一个栈s，存放目前正在求解强连通分量的点。设当前点为u，存在一条(u->v)的边，若v不在栈内，说明他有可能成为当前强连通分量的一员，就将它加入到当前正在求解的强连通分量的点集中，即入栈。若v在栈内，说明形成了一个环，当前求解的强连通分量成立（因为通过环可以访问到每一个节点），可以开始维护答案，即在环中找一个dfs序最小的点作为根节点，维护环中每一个节点的low值，通过dfs的递归特点可以很好的实现。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
#define bl(u) for(int i=head[u];i;i=e[i].nxt)
using namespace std;
const int N=1E4+10,M=1E5+10;
int n,m,tot,timer;
int head[N],in[N],insta[N],dfn[N],low[N],h_[N],anss[N],fa[N],a[N];
struct Edge{
	int frm,to,nxt;
}e[M],se[M];
stack<int> s;
inline void add_edge(int u,int v) {
	e[++tot].nxt=head[u];e[tot].frm=u;e[tot].to=v;head[u]=tot;
}
inline void add_(int u,int v) {
	se[++tot].nxt=h_[u];se[tot].frm=u;se[tot].to=v;h_[u]=tot;
}
inline int read() {
	int ret=0,flag=1;char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')ret=ret*10+ch-'0',ch=getchar();
	return ret*flag;
}
void tarjan(int u) {
	dfn[u]=low[u]=++timer;
	insta[u]=1;
	s.push(u);
	bl(u)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(insta[v])
			low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		int now;
		while(now=s.top())
		{
			fa[now]=u;
			s.pop();
			insta[now]=0;
			if(now==u)
				break;
			a[u]+=a[now];
		}
	}
}
int topo() {
	queue<int> q;
	rep(i,1,n)
	{
		if(fa[i]==i && !in[i])
		{
			q.push(i);
			anss[i]=a[i];
		}
	}
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=h_[u];i;i=se[i].nxt)
		{
			int v=se[i].to;
			--in[v];
			anss[v]=max(anss[v],anss[u]+a[v]);
			if(!in[v])
				q.push(v);
		}
	}
	rep(i,1,n)
	{
		anss[0]=max(anss[i],anss[0]);
	}
	return anss[0];
}
int main() {
	n=read();m=read();
	rep(i,1,n)
	{
		a[i]=read();
	}
	int u,v;
	rep(j,1,m)
	{
		u=read();v=read();
		add_edge(u,v);
	}
	rep(i,1,n)
		if(!dfn[i])
			tarjan(i);
	tot=0;
	rep(i,1,m)
	{
		int u=fa[e[i].frm],v=fa[e[i].to];
		if(u!=v)
		{
			add_(u,v);
			++in[v];
		}
	}
	cout<<topo()<<endl;
}