Tarjan+DP 93pts求调(wa on #14)
查看原帖
Tarjan+DP 93pts求调(wa on #14)
1016201
tjy_tansuper楼主2024/10/5 20:17

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int NUM=5e5+6;
int low[NUM],dfn[NUM],id[NUM];
vector<int> g[NUM],h[NUM];
int val[NUM],dis[NUM],rd[NUM],res[NUM];
bool b[NUM];
bool bar[NUM];
int n,m,cnt,scc;
stack<int> st;
void tarjan(int u){
	low[u]=dfn[u]=++cnt;
	st.push(u);
	for(int v:g[u]){
		if(!dfn[v]){
			tarjan(v); low[u]=min(low[u],low[v]);
		}
		else if(!id[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){//此时点u为当前搜索子树的根,此时从点u到栈顶的所有元素组成一个强连通分量
		id[u]=++scc; res[scc]=val[u];
		while(!st.empty()){
			int v=st.top(); st.pop();
			if(v==u) break;
			id[v]=scc;
			res[scc]+=val[v];//将所有点权加到根节点中,缩点 
			if(b[v]) bar[scc]=1;
		}
	}
}
void top_sort(int s){
	queue<int> q; 
	q.push(id[s]); dis[id[s]]=res[id[s]];
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v:h[u]){
			rd[v]--; dis[v]=max(dis[v],dis[u]+res[v]);
			if(rd[v]==0) q.push(v);
		}
	}
	int ans=0;
	for(int i=1;i<=scc;i++){
		if(bar[i]) ans=max(ans,dis[i]); 
	} 
	cout<<ans<<endl;
}
void solve(){
	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>>val[i];
	int s,p; cin>>s>>p;
	for(int i=1;i<=p;i++){
		int x; cin>>x;
		b[x]=1;
	}
	tarjan(s);
	for(int i=1;i<=n;i++){
	    if(id[i]==0) continue;
	    for(int v:g[i]){
	    	if(id[v]==id[i]) continue;
	    	rd[id[v]]++; h[id[i]].push_back(id[v]);
		}
	}
	top_sort(s);
}
signed main(){
	solve(); return 0;
}
2024/10/5 20:17
加载中...