TLE on #2#3#10,求调
查看原帖
TLE on #2#3#10,求调
551917
110821zj_hhx楼主2024/8/6 11:30
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,a[500005],root,p,ans,sum[500005],bar[500005],nbar[500005],f[500005],num,tot,dfn[500005],stk[500005],low[500005],dis[500005],top,v[500005];
vector<int>s[500005],ns[500005];
void tarjan(int x){
	dfn[x]=low[x]=++tot;
	stk[++top]=x,v[x]=1;
	for(int i=0;i<s[x].size();i++){
		if(!dfn[s[x][i]]){
			tarjan(s[x][i]);
			low[x]=min(low[x],low[s[x][i]]);
		}else{
			if(v[s[x][i]]) low[x]=min(low[x],dfn[s[x][i]]);
		}
	}
	if(dfn[x]==low[x]){
		num++;
		while(1){
			int t=stk[top];
			nbar[num]|=bar[t];
			sum[num]+=a[t];
			f[t]=num;
			v[t]=0;
			top--;
			if(t==x) break;
		}
	}
}
void make(){
	for(int x=1;x<=n;x++){
		for(int i=0;i<s[x].size();i++){
			if(f[x]==f[s[x][i]]) continue;
			ns[f[x]].push_back(f[s[x][i]]);
		}
	}
}
int dfs(int x,int fa,int cnt){
	for(int i=0;i<ns[x].size();i++){
		if(ns[x][i]==fa) continue;
		dfs(ns[x][i],x,cnt+sum[ns[x][i]]);
	}
	if(nbar[x]) ans=max(ans,cnt);
	return cnt;
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		s[x].push_back(y);
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d %d",&root,&p);
	for(int i=1;i<=p;i++){
		int x;
		scanf("%d",&x);
		bar[x]=1;
	} 
	tarjan(root);
	make();
	dfs(f[root],0,sum[f[root]]);
	printf("%d\n",ans);
	return 0;
}
2024/8/6 11:30
加载中...