萌新求助88pts WA#1#3
查看原帖
萌新求助88pts WA#1#3
114288
lijia123楼主2021/8/15 22:36
#include<bits/stdc++.h>
using namespace std;
queue<int> q;
struct sp{
	int next,to;
}a[500001],v[500001];
long long low[500001],dfn[500001],num=0,num1=0,cnt=0,cnt1=0,cost[500001],st[500001],s,k,m,n;
long long a1,a2,co[500001],head[5000001],cost1[500001],head1[5000001],num2=0,d[500001],w[500001],ans=0;
bool b[500001],vis[500001],c[500001];
void build(int from,int to)
{
	a[++num1].next=head[from];
	a[num1].to=to;
	head[from]=num1;
}
void build1(int from,int to)
{
	v[++num2].next=head1[from];
	v[num2].to=to;
	head1[from]=num2;
}
void trajan(int u)
{
	low[u]=dfn[u]=++num;
	st[++cnt]=u;
	for(int i=head[u];i;i=a[i].next)
	{
		int p=a[i].to;
		if(!dfn[p])
		{
			trajan(p);
			low[u]=min(low[u],low[p]);
		}
		else if(!co[p])
			low[u]=min(low[u],dfn[p]);
	}
	if(dfn[u]==low[u])
	{
		co[u]=++cnt1;cost1[cnt1]+=cost[u];
		if(b[u]) c[cnt1]=1;
		while(st[cnt]!=u)
		{
			if(b[st[cnt]]) c[cnt1]=1;
			cost1[cnt1]+=cost[st[cnt]];
			co[st[cnt]]=cnt1;
			--cnt;
		}
		--cnt;
	}
}
void spfa(int u)
{
	vis[u]=1;
	q.push(u);
	w[u]=cost1[u];
	if(c[u]) ans=max(ans,cost1[u]);
	while(!q.empty())
	{
		int p=q.front();q.pop();
		vis[p]=0;
		for(int i=head1[p];i;i=v[i].next)
		{
			int p1=v[i].to;
			if(vis[p1]) continue;
			w[p1]=max(w[p1],w[p]+cost1[p1]);
			if(c[p1]) ans=max(ans,w[p1]);
			q.push(p1);
			vis[p1]=1;
		}
	}
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%lld%lld",&a1,&a2);
		build(a1,a2);
		d[a1]++;
	}
	for(int i=1;i<=n;++i)
		scanf("%lld",&cost[i]);
	scanf("%lld%lld",&s,&k);
	for(int i=1;i<=k;++i)
	scanf("%lld",&a1),b[a1]=1;
	trajan(s);
	for(int i=1;i<=n;++i)
	{
			for(int j=head[i];j;j=a[j].next)
				if(co[a[j].to]!=co[i])
				build1(co[i],co[a[j].to]);
	}
	spfa(co[s]);
	cout<<ans;
}
2021/8/15 22:36
加载中...