@[dzn123456](/user/505081)
```cpp
vis[stc[iop]]=cnt; //
dia[cnt]+=dis[stc[iop]];
vis[stc[iop]]=0; //
```
另外你的思路好像复杂了。
正常缩点后拓扑排序就可以了
by Alphaban @ 2022-05-08 17:20:02
@[IcproX](/user/112109)
感谢大佬
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
queue <int> q;
vector <int> ss[100086];
vector <int> r2[100086];
int f[1000005],ne[1000005],v[1000005];
int top,cnt=-1,cntt;
int dfn[1000086],dia[1000086],low[1000086];
int stc[1000086],cnm,vis[1000086],visi[100086],iop;
int dis[1000086];
int h[1000086],r[1000005],ans[1000005];
void add(int x,int y){
ne[++top]=h[x];
f[top]=x;
v[top]=y;
h[x]=top;
}
void toto(){
for(int i=1;i<=cnt;i++){
if(r[i]==0)
q.push(i);
}
while(!q.empty()){
int k=q.front();
q.pop();
ans[++cntt]=k;
for(int i=1;i<=ss[k].size();i++){
r[ss[k][i-1]]--;
if(r[ss[k][i-1]]==0)
q.push(ss[k][i-1]);
}
}
}
void dfs(int x){
dfn[x]=low[x]=++cnm;
stc[++iop]=x;
vis[x]=1;
for(int i=h[x];i;i=ne[i]){
if(!dfn[v[i]]){
dfs(v[i]);
low[x]=min(low[x],low[v[i]]);
}
else
if(vis[v[i]]){
low[x]=min(low[x],dfn[v[i]]);
}
}
if(dfn[x]==low[x]){
cnt++;
while(1){
visi[stc[iop]]=cnt;
dia[cnt]+=dis[stc[iop]];
vis[stc[iop]]=0;
iop--;
if(x==stc[iop+1])
break;
}
}
}int x,y;
int anss=-1;
int f1[1000085];
int main(){
memset(h,-1,sizeof(h));
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>dis[i];
}
for(int i=1;i<=m;i++){
cin>>x>>y;
add(x,y);
}
for(int i=1;i<=n;i++){
if(!dfn[i])
dfs(i);
}
for(int i=1;i<=top;i++){
if(visi[f[i]]!=visi[v[i]])
{
x=visi[f[i]],y=visi[v[i]];
r[y]++;
ss[x].push_back(y);
r2[y].push_back(x);
}
}
toto();
for(int i=1;i<=cnt;i++){
int g=ans[i];
f1[g]=dia[g];
for(int j=1;j<=r2[g].size();j++)
f1[g]=max(f1[g],f1[r2[g][j-1]]+dia[g]);
}
for(int i=1;i<=cnt;i++){
anss=max(anss,f1[i]);
}
cout<<anss;
return 0;
}
```
已A
by depresses @ 2022-05-09 17:10:43