我错了同样的,调了半天dp初始化也没对,到底怎么写
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,x,y;
int cnt,cnt2,h[N],h2[N],w[N],w2[N];
struct edge{
int f,t,nx;
}e[N],e2[N];
int dfn[N],low[N],belong[N],depth,countStr;
bool ins[N];
int st[N],Top;
void tarjan(int u){
dfn[u]=low[u]=++depth;
st[++Top]=u;
ins[u]=1;
for(int i=h[u];~i;i=e[i].nx){
int v=e[i].t;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v])low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u]){
++countStr;
while(st[Top+1]!=u){
belong[st[Top]]=countStr;
w2[countStr]+=w[st[Top]];
Top--;
ins[st[Top]]=0;
}
}
}
int ind[N],dp[N];
queue<int>q;
void topodp(){
for(int i=1;i<=countStr;i++){
if(ind[i]==0)q.push(i);
dp[i]=w2[i];
}
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=h2[t];~i;i=e2[i].nx){
int u=e2[i].f,v=e2[i].t;
dp[v]=max(dp[v],dp[u]+w2[v]);
ind[v]--;
if(ind[v]==0)q.push(v);
}
}
}
int main(){
memset(h,-1,sizeof(h));
memset(h2,-1,sizeof(h2));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",w+i);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
e[++cnt]=(edge){
x,y,h[x]
};
h[x]=cnt;
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=cnt;i++){
int a=belong[e[i].f],b=belong[e[i].t];
if(a!=b){
ind[b]++;
e2[++cnt2]=(edge){
a,b,h2[a]
};
h2[a]=cnt2;
}
}
topodp();
int ans=-114514;
for(int i=1;i<=countStr;i++)ans=max(ans,dp[i]);
printf("%d",ans);
return 0;
}
by 262620zzj @ 2023-05-02 14:02:59