挂了#1 #3 #11
查看原帖
挂了#1 #3 #11
670455
ska_0x08楼主2022/7/27 15:45
#include <bits/stdc++.h>
using namespace std;
const long long N=500010;
long long n,m,a[N],s,p,P[N]={0},dfn[N],low[N],idx=0,instack[N]={0},cnt=0,bel[N],val[N]={0},ans=-1,dp[N],vis[N]={0};
vector <int> ed[N];
stack <int> stk;
vector <int> vec[N];
map < pair<int,int>,bool> mp;
void tarjan(long long u)
{
	idx++;
	dfn[u]=low[u]=idx;
	instack[u]=1;
	stk.push(u);
	for(long long v : ed[u])
	{
		if(!dfn[v]) tarjan(v);
		if(instack[v]) low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u])
	{
		cnt++;
		while(true)
		{
			long long k=stk.top();
			stk.pop();
			instack[k]=0;
			vec[cnt].push_back(k);
			bel[k]=cnt;
			val[cnt]+=a[k];
			if(k==u) break;
		}
	}
}
void dfs(long long rt)
{
	/*cout<<rt<<endl;*/
	if(P[rt]==1)
	ans=max(ans,dp[rt]);
	for(long long u : vec[rt])
		for(long long v : ed[u])
			{
				pair<int,int> cun;
				cun.first=rt;
				cun.second=bel[v];
				if(! mp[cun] && bel[v] != rt && ! vis[bel[v]] )
				{
					mp[cun]=1;
					vis[bel[v]]=1;
					dp[bel[v]]=max(dp[rt]+val[bel[v]],val[bel[v]]);
					dfs(bel[v]);
					vis[bel[v]]=0;
				}
			}
	
		
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=m;i++)
	{
		long long x,y;
		scanf("%lld%lld",&x,&y);
		ed[x].push_back(y);			
	}
	
	for(long long i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(long long i=1; i <= n ;i++)
		if(!dfn[i])
			tarjan(i);
	scanf("%lld%lld",&s,&p);
	for(long long i=1;i<=p;i++)
	{
		long long j;
		scanf("%lld",&j);
		P[bel[j]]=1;
	}	
	for(long long i=1;i<=cnt;i++)
		dp[i]=val[i];
	/*for(long long i=1;i<=n;i++)
	cout<<"("<<bel[i]<<")";*/
	dfs(bel[s]);
	printf("%lld",ans);
	return 0;
}
2022/7/27 15:45
加载中...