求调,40分,好像输出变成0了...c⌒っ゚Д゚)っ

P3387 【模板】缩点

您的tarjan板子写错了,还有新建图的时候最好还是新写一个add吧 ```cpp #include<bits/stdc++.h> using namespace std; #define N 200001 int ne[N],he[N],w[N],to[N],fr[N],k,p[N]; int low[N],ins[N],in[N],dfn[N],cnt,tot; int ru[N],dis[N],ans; int fr2[N],to2[N],ne2[N],he2[N]; stack<int> s; void tarjan(int x){ s.push(x); ins[x]=1; low[x]=dfn[x]=++cnt; for(int i=he[x];i;i=ne[i]){ int t=to[i]; if(!dfn[t]){ tarjan(t); low[x]=min(low[x],low[t]); } else if(ins[t])low[x]=min(low[x],dfn[t]); } if(low[x]==dfn[x]){ tot++; int t; while(t=s.top()){ ins[t]=0; in[t]=tot; p[tot]+=w[t]; s.pop(); if(t==x)break; } } } int topu(){ queue<int> q; for(int i=1;i<=tot;i++)if(!ru[i])q.push(i),dis[i]=p[i]; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=he2[x];i;i=ne2[i]){ int t=to2[i]; ru[t]--; dis[t]=max(dis[x]+p[t],dis[t]); if(ru[t]==0)q.push(t); } } for(int i=1;i<=tot;i++)if(dis[i]>ans)ans=dis[i]; return ans; } void add(int x,int y){ k++; fr[k]=x; to[k]=y; ne[k]=he[x]; he[x]=k; } void add2(int x,int y){ k++; fr2[k]=x; to2[k]=y; ne2[k]=he2[x]; he2[x]=k; } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); k=0; for(int i=1;i<=m;i++){ int t=in[to[i]],f=in[fr[i]]; if(f!=t){ add2(f,t); ru[t]++; } } //cout<<tot; cout<<topu(); //system("pause"); return 0; } ```
by _outcast_ @ 2021-08-22 10:51:26


@[xpeke](/user/376125) A掉了,谢谢大佬Thanks♪(・ω・)ノ
by __凉皮__ @ 2021-08-22 11:23:44


|