题目

AC on 2 6 8 10

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define debug cout<<"DEBUG"<<endl;
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define imp map<int,int>
using namespace std;
const int N=1e4+5,M=1e5+5; 
int n,m,a[N];
int h[N],h2[N],cnt=0;
struct node{
	int to,nxt;
}e[M],e2[M];
struct EDGE{
	int from,to;
}edge[M];
int dfn[N],low[N],scc[N],res=0,scc_cnt=0,val[N];
bool vis[N];
stack<int>st;
int rd[N],f[N];
void add1(int x,int y){
	e[++cnt].to=y;
	e[cnt].nxt=h[x];
	h[x]=cnt;
}
void add2(int x,int y){
	e2[++cnt].to=y;
	e2[cnt].nxt=h2[x];
	h2[x]=cnt;
}
void dfs(int x){
	dfn[x]=low[x]=++res;
	st.push(x);
	vis[x]=1;
	for(int i=h[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(!dfn[to]){
			dfs(to);
			low[x]=min(low[x],low[to]);
		}else if(vis[to]){
			low[x]=min(low[x],dfn[to]);
		}
	}
	if(dfn[x]==low[x]){
		scc_cnt++; 
		while(st.top()!=x){
			vis[st.top()]=0;
			scc[st.top()]=scc_cnt;
			val[scc_cnt]+=a[st.top()];
			st.pop();
		}
		vis[st.top()]=0;
		scc[st.top()]=scc_cnt;
		val[scc_cnt]+=a[st.top()];
		st.pop();
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add1(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) dfs(i);
	}
//	for(int i=1;i<=n;i++){
//		printf("%d ",scc[i]);
//	}
//	printf("\n");
//	for(int i=1;i<=scc_cnt;i++){
//		printf("%d\n",val[i]);
//	}
	cnt=0;
	for(int i=1;i<=m;i++){
		if(scc[edge[i].from]==scc[edge[i].to]) continue;
		add2(scc[edge[i].from],scc[edge[i].to]);
		rd[scc[edge[i].to]]++;
	}
	queue<int>q;
	for(int i=1;i<=scc_cnt;i++){
		if(!rd[i]){
			q.push(i);
			f[i]=val[i];
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=h2[x];i;i=e2[i].nxt){
			int to=e2[i].to;
			f[to]=max(f[to],f[x]+val[to]);
			rd[to]--;
			if(!rd[to]) q.push(to);
		}
	}
	int ans=0;
	for(int i=1;i<=scc_cnt;i++){
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}