关于我87pts wa#2#10
查看原帖
关于我87pts wa#2#10
520291
bktchizhi_fzh楼主2022/11/15 18:49

路过的大佬帮帮忙瞧一瞧把

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define N 500010
using namespace std;
int dfn[N],col[N],tot,tm,sum[N],low[N];
int vis[N],st[N],top;
int jiu[N],jius;
int n,m,a[N],s,p,u,v,bar[N],hd[N],sz,x;
int rd[N],dp[N],ans;
struct Eg{
	int nt,to,from;
}eg[2*N];
int siz,head[N];
struct Edge{
	int nt,to;
}edge[2*N];
queue<int>q;
void add(int from,int to){
	eg[++sz].nt=hd[from];
	eg[sz].to=to;
	eg[sz].from=from;
	hd[from]=sz;
}
void add_new(int from,int to){
	edge[++siz].nt=head[from];
	edge[siz].to=to;
	head[from]=siz;
}
void tarjan(int now){
	dfn[now]=low[now]=++tm;
	st[++top]=now;vis[now]=1;
	for(int i=hd[now];i;i=eg[i].nt){
		int to=eg[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}
		else if(vis[to])low[now]=(low[now],low[to]);
	}
	if(dfn[now]==low[now]){
		tot++;
		bool f=false;
		while(1){
			int to=st[top];
			top--;
			sum[tot]+=a[to];
			col[to]=tot;
			vis[to]=0;
			if(bar[to]&&(!f)){
				jiu[++jius]=tot;
				f=true;
			}
			if(to==now)break;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&u,&v),add(u,v);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d%d",&s,&p);
	for(int i=1;i<=p;i++)scanf("%d",&x),bar[x]=1;
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=m;i++){
		int x=col[eg[i].from];
		int y=col[eg[i].to];
		if(x!=y){
			add_new(x,y);
			rd[y]++;
		}
	}
	s=col[s];
	for(int i=1;i<=tot;i++)
		if((!rd[i])&&(i!=s))q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].nt){
			int to=edge[i].to;
			rd[to]--;
			if(rd[to]==0&&to!=s)q.push(to);
		}
	}
	q.push(s);
	dp[s]=sum[s];
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].nt){
			int to=edge[i].to;
			dp[to]=max(dp[to],dp[u]+sum[to]);
			rd[to]--;
			if(rd[to]==0)q.push(to);
		}
	}
	for(int i=1;i<=jius;i++)ans=max(ans,dp[jiu[i]]);
	printf("%d",ans);
	return 0;
}
2022/11/15 18:49
加载中...