比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 pcx 运行时间 0.219 s
代码语言 C++ 内存使用 26.76 MiB
提交时间 2025-08-13 09:31:21
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,w[N],p,s,b[N],dp[N];
int dfn[N],low[N],tim,id[N],cnt,sz[N];
bool in[N];
vector<int> g[N],sg[N];
stack<int> st;
void tarjan(int u){
	dfn[u]=low[u]=++tim;
	st.push(u);
	in[u]=1;
	for(size_t i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(in[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}	
	if(low[u]==dfn[u]){
		cnt++;
		while(1){
			int v=st.top();
			st.pop();
			in[v]=0;
			sz[cnt]+=w[v];
			id[v]=cnt;
			if(u==v) break;
		}
	}
	return;
}
void bfs(){
	queue<int> q;
	dp[id[s]]=sz[id[s]];
	q.push(id[s]);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(size_t i=0;i<sg[u].size();i++){
			int v=sg[u][i],va=sz[v];
			if(dp[v]<dp[u]+va){
				dp[v]=dp[u]+va;
				q.push(v);
			}
		}
	}
	return;
}
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	cin>>s>>p;
	for(int i=1;i<=p;i++){
		cin>>b[i];
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int u=1;u<=n;u++){
		for(size_t i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(id[u]!=id[v]){
				sg[id[u]].push_back(id[v]);
			}
		}
	}
	bfs();
	int ans=0;
	for(int i=1;i<=p;i++){
		ans=max(ans,dp[id[b[i]]]);
	}
	cout<<ans;
	return 0;
}