社区讨论
这样写没用拓扑 正确性保证吗
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 条回复,欢迎继续交流。
正在加载回复...