哪位大佬能帮忙看下这个87分的程序错在哪!感谢,万分感谢!!!
查看原帖
哪位大佬能帮忙看下这个87分的程序错在哪!感谢,万分感谢!!!
1000384
gan_ge楼主2023/5/1 16:34
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
bool in_stack[maxn];
int n,m,s,p;
int dfn[maxn],low[maxn],dfncnt=0,scc[maxn],scccnt=0,val[maxn];
vector<int> G[maxn];
stack<int> sm;
void dfs(int u){
	dfn[u]=low[u]=++dfncnt;
	in_stack[u]=1;
	sm.push(u);
	for(auto v:G[u]){
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in_stack[v])
			low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]){
		++scccnt;
		int y;
		do{
			y=sm.top();
			scc[y]=scccnt;
			in_stack[y]=0;
			sm.pop();
		}while(y!=u);
	}
}
int nn,nval[maxn],indegree[maxn];
vector<int> nG[maxn];
set<pair<int,int>> st;
void newGraph(){
	nn=scccnt;
	for(int u=1;u<=n;u++){
		nval[scc[u]]+=val[u];
		for(auto v:G[u]){
			int nu=scc[u],nv=scc[v];
			if(nu!=nv)
				st.insert({nu,nv});
		}
	}
	for(auto e:st){
		int nu=e.first,nv=e.second;
		nG[nu].push_back(nv);
		indegree[nv]++;
	}
}
queue<int> q;
int dp[maxn];
void topo() {
	q.push(scc[s]);
	while(!q.empty()) {
		int u=q.front(); 
		q.pop();
		dp[u]+=nval[u];
		for(auto v:nG[u]) {
			dp[v]=max(dp[v],dp[u]);
			indegree[v]--;
			if(indegree[v]==0)
				q.push(v);	
		}
	}
}
int 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;i++)
		cin>>val[i];
	cin>>s>>p;	
	dfs(s);
	newGraph();
	topo();
	int ans=0;
	for(int i=1;i<=p;i++){
		int k;
		cin>>k;
		ans=max(ans,dp[scc[k]]);
	}		
	cout<<ans;
	return 0;
}
2023/5/1 16:34
加载中...