社区讨论

这样写没用拓扑 正确性保证吗

P3387【模板】缩点参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mib2m5zi
此快照首次捕获于
2025/11/23 10:00
3 个月前
此快照最后确认于
2025/11/23 12:42
3 个月前
查看原帖
新图跑dp从后往前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,ans,dp[N];
int scc[N],dfn[N],w[N],w2[N],low[N],size[N],Sta[N],cnt,top,tot,in[N],out[N];
bool inS[N];
vector<int> e[N],e2[N];
void tarjan(int x){
	dfn[x]=low[x]=++tot;
	Sta[++top]=x,inS[x]=1;
	for(auto y:e[x]){
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(inS[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		int y;cnt++;
		do{
			y=Sta[top--];
			inS[y]=0;
			scc[y]=cnt;
			size[cnt]++;
		}while(y!=x);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		e[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++){
		w2[scc[i]]+=w[i];
		for(auto v:e[i]){
			if(scc[i]!=scc[v]){
				e2[scc[i]].push_back(scc[v]);
			}
		}
	}
	for(int i=cnt;i>=1;i--){
		if(dp[i]==0){
			dp[i]=w2[i];
		}
		for(auto y:e2[i]){
			dp[y]=max(dp[y],dp[i]+w2[y]);
		}
	}
	for(int i=1;i<=cnt;i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...