缩点+记忆化搜索

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=50005;
vector<int>e[maxn];
vector<int>g[maxn];
int scc[maxn],val[maxn],tot;
//scc[i]节点i所在的scc
//val[i]第i个scc的价值 
int n,m,cnt;
int w[maxn],low[maxn],dfn[maxn];
stack<int>st;
bool inst[maxn],vis[maxn];
int f[maxn];
void tarjan(int u){
	low[u]=dfn[u]=++cnt;
	st.push(u);inst[u]=true;
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(dfn[v]==0){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(inst[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]!=dfn[u])return;
	++tot;
	while(st.top()!=u){
		scc[st.top()]=tot;
		val[tot]+=w[st.top()];
		st.pop();
	}
	scc[u]=tot,val[tot]+=w[u];
	inst[u]=false;st.pop();
}
int dp(int u){
	if(f[u]!=-1)return f[u];
	int ans=0;vis[u]=true;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(vis[v])continue;
		ans=max(ans,dp(v));
	}
	f[u]=ans+val[u];
	vis[u]=false;
	return f[u];
}
int main(){
//	freopen("P3387_1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0)tarjan(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<e[i].size();j++){
			int v=e[i][j];
			if(scc[i]==scc[v])continue;
			g[scc[i]].push_back(scc[v]);
		}
	}
	for(int i=1;i<=tot;i++){
		f[i]=-1;
	}
	int ans=0;
	for(int i=1;i<=tot;i++){
		ans=max(ans,dp(i));
	}
	printf("%d",ans);
	return 0;
}