@[SakurajiamaMai](/user/784813)
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,M=1e4+10;
int n,m,a[N],res,dist[N],id[N],p[N],kk[N];
int e[N],ne[N],h[N],w[N],idx;
int dfn[N],low[N],_size[N],_stack[N];
int times,top,scc_num;
bool vis[N];
vector<int>F[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
low[u]=dfn[u]=++times;
_stack[++top]=u,vis[u]=true;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]) tarjan(j),low[u]=min(low[u],low[j]);
else if(vis[j]) low[u]=min(low[u],dfn[j]);
}
if(low[u]==dfn[u]){
int y;
++scc_num;
do{
y=_stack[top--];
vis[y]=false,id[y]=scc_num;
kk[scc_num]+=a[y];
if(u==y) break;
}while(y!=u);
}
}
void topsort()
{
queue<int>que;
for(int i=1;i<=scc_num;i++){
if(!p[i]) que.push(i),dist[i]=kk[i];
}
while(!que.empty()){
int now=que.front(); que.pop();
for(int j:F[now]){
p[j]--,dist[j]=max(dist[j],dist[now]+kk[j]);
if(p[j]==0) que.push(j);
}
}
}
signed main()
{
cin>>n>>m;
memset(h, -1, sizeof h);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
add(x,y);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++)
for(int j=h[i];j!=-1;j=ne[j]){
int k=e[j];
int x=id[i],y=id[k];
if(x!=y) F[x].push_back(y),p[y]++;
}
topsort();
for(int i=1;i<=n;i++) res=max(res,dist[i]);
cout<<res<<endl;
return 0;
}
```
调过了,问题很多
by Nwayy @ 2023-08-08 16:17:31
1. 必须重新建图,你原来的 ```id[j]``` 也应该改成 ```id[i]```。
1. 拓扑函数里面你遍历应该是遍历强连通分量个数啊,看不懂你遍历 $n$ 是什么鬼。
1. 最好开个新数组记录每个强连通分量的边权和。
by Nwayy @ 2023-08-08 16:19:35
@[Nwayy](/user/664744) 谢带佬,里面有些问题我意识到了,多谢指正
by SakurajiamaMai @ 2023-08-08 18:03:06