比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 李奇文 运行时间 0.135 s
代码语言 C++ 内存使用 15.45 MiB
提交时间 2025-08-13 09:27:37
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,S,P,ans,ca[N];
int hd[N],tot,tp,w[N],yj[N];
int a[N],dr[N],ins[N],dfn[N],low[N],s[N],cnt;
int sc,scc[N],sz[N];
struct node{
	int to,nxt;
}e[N];
void add(int x,int y){
	++tot;
	e[tot].to=y;
	e[tot].nxt=hd[x];
	hd[x]=tot;
}
void tarjan(int u){
	low[u]=dfn[u]=++cnt,s[++tp]=u,ins[u]=1;
	for(int i=hd[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(dfn[v]==0){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(ins[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++sc;
		do{
			scc[s[tp]]=sc;
			sz[sc]++;
			ins[s[tp]]=0;
		}while(s[tp--]!=u);
	}
}
vector<int> newe[N];
void spfa(){
	ca[scc[S]]=w[scc[S]];
	queue<int> q;
	q.push(scc[S]);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<newe[u].size();i++){
			int v=newe[u][i];
			if(ca[u]+w[v]>ca[v]){
				ca[v]=ca[u]+w[v];
				q.push(v);
			}
		}
	}
}
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int hs,sh;
		scanf("%d%d,",&hs,&sh);
		add(hs,sh);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=hd[i];j;j=e[j].nxt){
			int v=e[j].to;
			if(scc[i]==scc[v]) continue;
			newe[scc[i]].push_back(scc[v]);
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		w[scc[i]]+=a[i];
	}
	scanf("%d%d",&S,&P);
	for(int i=1;i<=P;i++){
		scanf("%d",&dr[i]);	
	}
	for(int i=1;i<=n;i++){
		if(dr[i]) yj[scc[dr[i]]]=1;
	}
	spfa();
	for(int i=1;i<=sc;i++){
		if(yj[i]) ans=max(ans,ca[i]);
	}
	printf("%d",ans);
	return 0;
}