自己测试应该是拓扑排序有问题,但找不出哪里写错了,跪求调
#include<bits/stdc++.h>
using namespace std;
const int kMax=1e4+4;
const int maxn=1e5+6;
int dfn[kMax],low[kMax];
vector<int> edge[maxn];
vector<int> G[maxn];//新图
bool vis[kMax];
int n,m,top,tot;
int in[kMax],to[kMax];
int st[kMax];
int col[kMax],cnt;//新点的编号,数量
int ind[kMax];
int dis[kMax],w[kMax];
int f[kMax];
void tarjan(int index)
{
vis[index]=1;
dfn[index]=low[index]=tot++;
st[++top]=index;
for(int i=0;i<edge[index].size();i++)
{
int temp=edge[index][i];
if(!dfn[temp])
{
tarjan(temp);
low[index]=min(low[index],low[temp]);
}
else if(vis[temp])//in stack
{
low[index]=min(low[index],dfn[temp]);
}
}
if(dfn[index]==low[index])
{
cnt++;
while(st[top+1]!=index)
{
w[cnt]+=dis[st[top]];
col[st[top]]=cnt;
vis[st[top--]]=0;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>dis[i];
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
in[i]=u;
to[i]=v;
edge[u].push_back(v);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
// for(int i=1;i<=cnt;i++) cout<<w[i]<<endl;
for(int i=1;i<=m;i++)
{
if(col[in[i]]!=col[to[i]])
{
G[col[in[i]]].push_back(col[to[i]]);
ind[col[to[i]]]++;
// cout<<col[in[i]]<<" "<<col[to[i]]<<endl;
}
}
queue<int> q;
for(int i=1;i<=cnt;i++)
{
if(!ind[i])
{
q.push(i);
f[i]=w[i];
}
}
int ans=0;
while(!q.empty())
{
int inn=q.front();
q.pop();
for(int i=0;i<G[inn].size();i++)
{
int too=G[inn][i];
ind[too]--;
f[too]=max(f[inn]+w[inn],f[too]);
if(!ind[too]) q.push(too);
}
ans=max(ans,f[inn]);
}
// for(int i=1;i<=cnt;i++)
// {
// ans=max(ans,f[i]);
// }
cout<<ans<<endl;
return 0;
}