比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 左清源 运行时间 0.218 s
代码语言 C++ 内存使用 26.92 MiB
提交时间 2025-08-13 09:24:29
显示代码纯文本
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=5e5+10;
vector<int>G[N],F[N];
int n,m,st,dfn[N],low[N],col[N];
int cnt,mk[N],stk[N],top,p,ans,ind[N]; 
int scc,val[N],w[N],dp[N],vis[N];
void add(int x,int y){
	G[x].push_back(y); 
}
void link(int x,int y){
	F[x].push_back(y); 
}
void tarjan(int u){
	dfn[u]=low[u]=++cnt;
	mk[u]=1,stk[++top]=u;
	for(auto v:G[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(mk[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		scc++;
		while(stk[top+1]!=u){
			int v=stk[top--];
			mk[v]=0;col[v]=scc;
			val[scc]+=w[v];
		}
	}
	return;
}
void dfs(int x){
	vis[x]=1;
	for(auto y:F[x])if(!vis[y])dfs(y);
	return;
}
queue<int>q;
void topsort(int s){
	q.push(s);
	dp[s]=val[s];
	while(q.size()){
		int x=q.front();q.pop();
		for(auto y:F[x]){
			if(!vis[y])continue;
			dp[y]=max(dp[y],dp[x]+val[y]);
			ind[y]--;
			if(!ind[y])q.push(y);
		}
	}
	for(int i=1;i<=scc;i++)if(mk[i])ans=max(ans,dp[i]);
	return;
}
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d %d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++)scanf("%d",w+i);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	scanf("%d %d",&st,&p);
	for(int i=1;i<=p;i++){
		int x;scanf("%d",&x);
		mk[col[x]]=1;
	}
	for(int i=1;i<=n;i++){
		for(auto j:G[i]){
			if(col[i]!=col[j]){
				link(col[i],col[j]);
				//cout<<col[i]<<" "<<col[j]<<endl;
			}
		}
	}
	dfs(col[st]);
	for(int i=1;i<=n;i++){
		for(auto j:G[i]){
			if(col[i]!=col[j]&&vis[col[i]]&&vis[col[j]]){
				ind[col[j]]++;
			}
		}
	}
	topsort(col[st]);
	printf("%d\n",ans);
	return 0;
}