40分WA求助

P3387

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N=1000005;
int c,cc,t,cnt,n,m;
int a[N];
int head[N],stack[N],sd[N],low[N],dfn[N];
int head2[N],in[N],dis[N];
bool v[N];
struct Edge
{
	int from,to,last;
}edge[N*10],edge2[N*10];
void add(int u,int v)
{
	c++;
	edge[c].from=u;
	edge[c].to=v;
	edge[c].last=head[u];
	head[u]=c;
	return; 
}
void add2(int x,int y)
{
	cc++;
	edge2[cc].from=x;
	edge2[cc].to=y;
	edge2[cc].last=head2[x];
	head2[x]=cc;
	in[y]++;
	return;
}
void tarjan(int x)
{
	low[x]=dfn[x]=++t;
	stack[++cnt]=x;
	v[x]=1;
	for(int i=head[x];i;i=edge[i].last){
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(v[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		int z;
		while(z=stack[cnt--]){
			
			sd[z]=x;
			v[z]=0;
			if(x==z) break;
			a[x]+=a[z];
		}
	}
	return;
}
queue<int> r;
int topo()
{
	for(int i=1;i<=n;i++) 
		if(!in[i]){
			r.push(i);
			dis[i]=a[i];
		}
	while(!r.empty()){
		int x=r.front();
		r.pop();
		for(int i=head2[x];i;i=edge2[i].last){
			int y=edge2[i].to;
			dis[y]=max(dis[y],dis[x]+a[y]);
			in[y]--;
			if(!in[y]) r.push(y);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(m--){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=m;i++){
		int x=sd[edge[i].from],y=sd[edge[i].to];
		if(x!=y) add2(x,y);
		
	}
	cout<<topo();
	return 0;
}