题目链接

大概率是建图和拓扑dp的问题。

#include<bits/stdc++.h>
using namespace std;
vector<int> g[500010];
vector<int> b[500010];
int low[500010],dfn[500010];
int cnt,tot;
stack<int> s;
bool ins[500010];
int a[500100];
int id[500010];
void dfs(int u){
	cnt++;
	dfn[u] = low[u] = cnt;
	ins[u] = 1;
	s.push(u);
	for(int v:g[u]){
		if(!dfn[v]){
			dfs(v);
			low[u] = min(low[v],low[u]);
		}
		else if(ins[v]){
			low[u] = min(low[u],low[v]);
		}
	}
	
	if(low[u] == dfn[u]){
		int node;
		tot++;
		do{
			node = s.top();
			id[node] = tot;
			b[tot].push_back(node);
			s.pop();
			ins[node] = 0;
		}
		while(node != u);
	}
}
int n,m;

vector<int> gg[500010];
int in[500010],S,P;
int val[500010],dp[500010];
bool pd[500010];
void topu(){
	int ans = 0;
	vector<int> q;
	
	q.push_back(id[S]);
	dp[0] = -1e9-7;
	for(int i=1;i<=tot;i++){
	
		dp[i] = -(1e9+7);
		if (in[i]==0) q.push_back(i);
	}
	dp[id[S]] = val[id[S]];
	for(int i = 0;i < q.size();i++){
		int u = q[i];
		//cout<<dp[u]<<endl;
		//if(pd[u])ans = max(ans,dp[u]);
		for(int v:gg[u]){
		 	in[v]--;
		 	dp[v] = max(dp[v],dp[u]+val[v]);

		 	if(in[v] == 0){
		 		q.push_back(v);
			}
		}
	}
	for(int i = 1;i <= tot;i++){
		if(pd[i]){
			ans = max(ans,dp[i]);
		}
	}
	//cout<<ans;
}
//bool pd[100010];
int main(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i = 1;i <= n;i++){
		cin>>a[i];
	}
	for(int i = 1;i <= n;i++){
		if(!dfn[i])dfs(i);
	}
	int cnt = 0;
	cin>>S>>P;
	for(int i = 1;i <= P;i++){
		int x;
		cin>>x;
		pd[id[x]] = 1;
	}
	for(int i = 1;i <= n;i++){
		val[id[i]] += a[i];
		for(int v:g[i]){
			if(id[v] != id[i]){
				gg[id[i]].push_back(id[v]);
				in[id[v]]++;
			}
		}
	}
	topu();
	int ans = 0;
	for(int i=1;i<=tot;i++)
		if (pd[i]&&dp[i]>ans)
			ans=dp[i];
	printf("%d",ans);

	return 0;
}