评测记录

#include <bits/stdc++.h>
using namespace std;

const int N = 10100;
const int M = 100100;
int n,m,ans;
int a[N];
int dfn[N],low[N];
int front[N],head[M],nxt[M],to[M];
int s[N],top;
int cnt;
bool in[N];
int sc[N],scc;
int q[N];
int d[N],dp[N];
queue <int> que;

void dfs(int x){
	dfn[x] = ++cnt;
	low[x] = dfn[x];
	
	s[++top] = x;
	in[x] = true; 
	for(int i = head[x];i;i = nxt[i]){
		if(!dfn[to[i]]){
			dfs(to[i]);
			low[x] = min(low[x],low[to[i]]);
		}else{
			if(in[to[i]]){
				low[x] = min(low[x],low[to[i]]);
			}
		}
		if(dfn[x] == low[x]){
			in[x] = false;
			sc[x] = ++scc;
			q[scc] = a[x];
			while(s[top] != x){
				q[scc] += a[s[top]];
				sc[s[top]] = scc;
				in[s[top--]] = false;
			}
			top--;
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	int x,y;
	for(int i = 1;i <= m;i++){
		cin >> x >> y;
		front[i] = x;
		to[i] = y;
		nxt[i] = head[x];
		head[x] = i;
	}
	
	for(int i = 1;i <= n;i++){
		if(!dfn[i]){
			dfs(i);
		}
	}
//	for(int i = 1;i <= n;i++){
//		cout << sc[i] << " ";
//	} 
	memset(head,0,sizeof(head));
	for(int i = 1;i <= m;i++){
		x = sc[front[i]];
		y = sc[to[i]];
		if(x == y){
			continue;
		}
		nxt[i] = head[x];
		head[x] = i;
		to[i] = y;
		d[y]++;
	}
	
	for(int i = 1;i <= scc;i++){
		if(!d[i]){
			que.push(i);
		}
	}
	while(!que.empty()){
		int k = que.front();
		que.pop();
		dp[k] += q[k];
		ans = max(ans,dp[k]);
		for(int i = head[k];i;i = nxt[i]){
			dp[to[i]] = max(dp[to[i]],dp[k]);
			if(!--d[to[i]]){
				que.push(to[i]);
			}
		}
	}
	
	cout << ans;
	
	return 0;
}