将单个scc的非top点的边全都转移到top点上处理

在某种特殊数据里应该会更优（

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

int n,m;

struct edge{
	int fr,to,ne;
}e[150005];
int h[10005],cnt;
void ade(int u,int v){
	e[++cnt]={u,v,h[u]},h[u]=cnt;
}

int dfn[10005],low[10005],sccnt;
stack<int>s;
bool ins[10005];
vector<int>scc[10005];
int inscc[10005];
int t;
void tarjan(int u){
	low[u]=dfn[u]=++t;
	s.push(u);
	ins[u]=1;
	for(int i=h[u];i;i=e[i].ne){
		int to=e[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[u]=min(low[u],low[to]);
		}
		else if(ins[to]==1){
			low[u]=min(low[u],dfn[to]);
		}
	}
	if(low[u]==dfn[u]){
		sccnt++;
		int f=s.top();
		while(1){
			int top=s.top();
			s.pop();
			scc[sccnt].push_back(top);
			ins[top]=0;
			inscc[top]=sccnt;
			if(top==u){
				break; 
			}
		}
	}
}

int inn[10005];
int flag[10005];
int a[10005];

queue<int>q;
int ans[10005],anss;
void topo(){
	for(int i=1;i<=n;i++){
		if(!flag[i]&&inn[i]==0){
			q.push(i);
			ans[i]=a[i];
		}
	}
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=h[u];i;i=e[i].ne){
			int to=e[i].to;
			if(inscc[u]==inscc[to]) continue;
			if(flag[to]) to=scc[inscc[to]][0];
			inn[to]--;
			ans[to]=max(ans[to],ans[u]+a[to]);
			if(inn[to]==0) q.push(to);
		}
		anss=max(anss,ans[u]);
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		ade(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=sccnt;i++){
		for(int j=1;j<scc[i].size();j++){
			a[scc[i][0]]+=a[scc[i][j]];
			int now=scc[i][j];
			flag[now]=1;
			for(int k=h[now];k;k=e[k].ne){
				int to=e[k].to;
				if(inscc[to]!=i){
					ade(scc[i][0],to);
				}
			}
		}
	}
	for(int i=1;i<=cnt;i++){
		int fr=e[i].fr,to=e[i].to;
		if(inscc[fr]==inscc[to]) continue;
		if(flag[fr]) continue;
		if(flag[to]) to=scc[inscc[to]][0];
		inn[to]++;
	}
	topo();
	cout<<anss<<endl;
}