萌新刚学OI,0pts请求DEBUG
查看原帖
萌新刚学OI,0pts请求DEBUG
922691
Hisy楼主2024/8/6 13:16
#include<bits/stdc++.h>
#define MAXN 500005
#define MAXM 500005
#define INF 1ll<<62 
using namespace std;
typedef long long ll;
struct node{
	int to,next;
	node()=default;
	node(int to,int next){
		this->to=to;
		this->next=next;
	}
}edge[MAXM];
int n,m,cnt,tim,fa[MAXN],head[MAXN],low[MAXN],dfn[MAXN],x[MAXM],y[MAXM];
bool vis[MAXN];
stack<int> stk;
ll money[MAXN],dis[MAXN];
template<typename value_type>
inline void memory_set(value_type *a,value_type val,size_t max_size){
	for(size_t i=0;i<max_size;++i){
		a[i]=val;
	}
}
inline void addedge(int x,int y){
	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;
			}
		}
	}
}
inline void spfa(int start){
	memory_set<bool>(vis,false,MAXN);
	memory_set<ll>(dis,-INF,MAXN);
	queue<int> q;
	q.push(start);
	dis[start]=money[start];
	vis[start]=true;
	while(!q.empty()){
		int front=q.front();
		q.pop();
		vis[front]=false;
		for(int i=head[front];i;i=edge[i].next){
			int to=edge[i].to;
			if(dis[to]<dis[front]+money[to]){
				dis[to]=dis[front]+money[to];
				if(!vis[to]){
					vis[to]=true;
					q.push(to);
				}
			}
		}
	}
}
inline void rebuild(){
	cnt=0;
	memory_set<int>(head,0,MAXN);
	memory_set<node>(edge,node(0,0),MAXM);
	for(int i=1;i<=m;++i){
		if(fa[x[i]]!=fa[y[i]]){
			addedge(fa[x[i]],fa[y[i]]);
		}
	}
	for(int i=1;i<=n;++i){
		ll now;
		cin>>now;
		money[fa[i]]+=now;
	}
	for(int i=1;i<=n;++i){
	    money[i]=money[fa[i]];
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>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);
		}
	}
	rebuild();
	int start,p;
	cin>>start>>p;
	spfa(start);
	ll ans=0;
	while(p--){
		int now;
		cin>>now;
		ans=max(ans,dis[now]);
	}
	cout<<ans;
	return 0;
}
2024/8/6 13:16
加载中...