大佬求调,调了一上午没看出来问题在哪
谢谢神犇们!!!
#include<bits/stdc++.h>
using namespace std;
#define next Next
const int N=400005;
int n,m;
int a[N];
int cnt=1;
int head[N];
int next[N],ver[N];
int cnt_c=1;
int head_c[N];
int next_c[N],ver_c[N];
int in[N];
int num=0;
int top=0;
int st[N];
bool ins[N];
int res=0;
int sum[N];
int dfn[N],low[N];
bool c[N];
int scc[N];
void add(int u,int v){
next[cnt]=head[u];
ver[cnt]=v;
head[u]=cnt++;
}
void add_c(int u,int v){
next_c[cnt_c]=head_c[u];
ver_c[cnt_c]=v;
head_c[u]=cnt_c++;
in[v]++;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
st[++top]=x;
ins[x]=true;
for(int i=head[x];i;i=next[i]){
int y=ver[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[ver[i]])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
res++;
int z;
while(z!=x){
z=st[top--];
ins[z]=false;
c[z]=res;
scc[res]+=a[z];
}
}
}
int topo(){
int dp[N];
queue<int> q;
for(int i=1;i<=res;i++){
dp[i]=scc[i];
if(!in[i])
q.push(i);
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head_c[x];i;i=next_c[i]){
int y=ver_c[i];
dp[y]=max(dp[y],dp[x]+sum[y]);
in[y]--;
if(!in[y])
q.push(y);
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dp[i]);
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
if(u==v) continue;
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i]){
top=0;
tarjan(i);
}
for(int x=1;x<=n;x++)
for(int i=head[x];i;i=next[i]){
int y=ver[i];
if(c[x]==c[y]) continue;
add_c(c[x],c[y]);
}
cout<<topo();
return 0;
}