WA0pts求调
查看原帖
WA0pts求调
959548
youwhenway_second楼主2024/11/24 15:52
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],a2[500005],beg;
vector<int> g[500005],b[500005];
set<int> g2[500005];
stack<int> sta;
int root[500005],belong[500005],dfn[500005],low[500005],times,belcnt;
bool ins[500005],vis[500005],is[500005],is2[500005];
void tarjan(int u){
	dfn[u]=low[u]=++times;
	ins[u]=1;
	sta.push(u);
	for (auto&v:g[u]){
		if (!dfn[v]){
			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]){
		belcnt++;
		int j;
		do{
			j=sta.top();
			sta.pop();
			ins[j]=0;
			belong[j]=belcnt;
		}while(j!=u);
	}
}
int dp[500005];
int dfs(int u){
	if (dp[u]!=-1)return dp[u];
	int res=0;
	for (auto&v:g2[u])res=max(res,dfs(v)+a2[u]);
	if (is2[u])return dp[u]=max(a2[u],res);
	return dp[u]=res;
}
signed 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;cin>>a[i++]);
	int ppp;
	cin>>beg>>ppp;
	for (int i=0;i<ppp;i++){
		int x;
		cin>>x;
		is[x]=1;
	}
	for (int i=1;i<=n;i++)if (!dfn[i])tarjan(i);
	for (int i=1;i<=n;i++){
		b[belong[i]].push_back(i);
		if (is[i])is2[belong[i]]=1;
	}
	memset(dp,-1,sizeof dp);
	for (int i=1;i<=belcnt;i++){
		int sum=0;
		for (auto&j:b[i]){
			sum+=a[j];
			for (auto&k:g[j])if (belong[k]!=i){
				g2[i].insert(belong[k]);
			}
		}
		a2[i]=sum;
	}
	cout<<dfs(belong[1]);
	return 0;
}
2024/11/24 15:52
加载中...