萌新刚学OI,0pts请求DEBUG
查看原帖
萌新刚学OI,0pts请求DEBUG
922691
Hisy楼主2024/7/22 15:21
#include<bits/stdc++.h>
#define MAXN 500005
#define MAXM 500005
using namespace std;
struct node{
	int from,to,next;
}edge[MAXM];
int n,m,cnt,tim,fa[MAXN],money[MAXN],head[MAXN],low[MAXN],dfn[MAXN],dis[MAXN],x[MAXM],y[MAXM];
bool vis[MAXN];
stack<int> stk;
inline void addedge(int x,int y){
	edge[++cnt].from=x;
	edge[cnt].to=y;
	edge[cnt].next=head[x];
	head[x]=cnt;
}
inline void tarjan(int now){
	vis[now]=true;
	dfn[now]=low[now]=++tim;
	stk.push(now);
	for(int i=head[now];i;i=edge[i].next){
		int to=edge[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}else if(vis[to]){
			low[now]=min(low[now],low[to]);
		}
	}
	if(low[now]==dfn[now]){
		while(true){
			int top=stk.top();
			stk.pop();
			fa[top]=now;
			vis[top]=false;
			if(top==now){
				return;
			}
			money[now]+=money[top];
		}
	}
}
inline void spfa(int start){
	queue<int> q;
	q.push(start);
	dis[start]=money[start];
	vis[start]=true;
	while(!q.empty()){
		int front=q.front();
		q.pop();
		for(int i=head[front];i;i=edge[i].next){
			int to=edge[i].to;
			vis[to]=true;
			if(dis[to]<dis[front]+money[to]){
				dis[to]=dis[front]+money[to];
				if(vis[to]){
					continue;
				}
				vis[to]=true;
				q.push(to);	
			}
		}
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d %d",&x[i],&y[i]);
		addedge(x[i],y[i]);
	}
	for(int i=1;i<=n;++i){
		fa[i]=i;
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	cnt=0;
	memset(head,0,sizeof(head));
	memset(edge,0,sizeof(edge));
	for(int i=1;i<=m;++i){
		if(fa[x[i]]!=fa[y[i]]){
			addedge(x[i],y[i]);
		}
	}
	for(int i=1;i<=n;++i){
		int now;
		scanf("%d",&now);
		money[fa[i]]+=now;
	}
	int start,p;
	scanf("%d %d",&start,&p);
	memset(vis,false,sizeof(vis));
	memset(dis,0,sizeof(dis));
	spfa(start);
	int ans=0;
	while(p--){
		int now;
		scanf("%d",&now);
		ans=max(ans,dis[fa[now]]);
	}
	printf("%d",ans);
	return 0;
}
2024/7/22 15:21
加载中...