求问P3387 玄关

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,idx=1,flag[N],is_stack[N],qlt=0,out[N],final[N],in[N];
stack<int>st;
struct p
{
	int low,dfn;
}a[N];
vector<int>v[N];
vector<int>v2[N];
vector<int>ans[N];
int bk[N];
int flagsd[N];
int dq[N],sum[N];
int dp[N];
queue<int>q;
void tarjan(int now,int dad)
{
	st.push(now);
	is_stack[now]=1;
	flag[now]=1;
	a[now].dfn=a[now].low=idx;
	idx++;
	for(auto p:v[now])
	{
		if(flag[p]==0)
		{
			tarjan(p,now);
			a[now].low=min(a[now].low,a[p].low);
		}
		else if(flag[p]==1&&is_stack[p]==1)
		{
			a[now].low=min(a[now].low,a[p].dfn);
		}
	}
	if(a[now].low==a[now].dfn)
	{
		qlt++;
		bk[now]=qlt;
		sum[qlt]+=dq[now];
		ans[qlt].push_back(now);
		while(st.top()!=now)
		{
			sum[qlt]+=dq[st.top()];
			is_stack[st.top()]=0;
			ans[qlt].push_back(st.top());
			bk[st.top()]=qlt;
			st.pop();
		}
		st.pop();
		is_stack[now]=0;
	}
	return;
}
void suodian(int now)
{
	flagsd[now]=1;
	for(auto p:v[now])
	{
		if(flagsd[p]==0)
		{
			suodian(p);
			if(bk[p]!=bk[now])
			{
				v2[bk[now]].push_back(bk[p]);
				in[bk[p]]++;
			}
		}
	}
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>dq[i];
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(flag[i]==0)
		{
			idx=1;
			tarjan(i,0);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(flagsd[i]==0)
		{
			suodian(i);
		}
	}
	for(int i=1;i<=qlt;i++)
	{
		if(in[i]==0)
		{
//			cout<<sum[i]<<endl;
			q.push(i);
			dp[i]=sum[i];
		}
	}
	while(q.size()>=1)
	{
		int x=q.front();
		q.pop();
		for(auto p:v2[x])
		{
			dp[p]=max(dp[p],dp[x]+sum[p]);
			in[p]--;
			if(in[p]==0)
			{
				q.push(p);
			}
		}
	}
	int maxn=0;
	for(int i=1;i<=qlt;i++)
	{
		maxn=max(maxn,dp[i]);
	}
	cout<<maxn;
	return 0;
}/*
7 6
1 2 3 4 5 6 7
1 2
1 3
4 5
5 6
6 7
2 3
*/

void suodian(int now)
{
	flagsd[now]=1;
	for(auto p:v[now])
	{
		if(bk[p]!=bk[now])
		{
			v2[bk[now]].push_back(bk[p]);
			in[bk[p]]++;
		}
		if(flagsd[p]==0)
		{
			suodian(p);
		}
	}
	return;
}