RT,目前已知缩点部分大概没有问题,问题可能在存第二个图的地方左右。。。求大佬帮忙看看Orz
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+120,maxm=2e5+10;
int head[maxn],head1[maxn],dis[maxn],dfsn[maxn],low[maxn],stak[maxn],sum[maxn];
int n,m;
int cnt1,cnt2,cnt,tim,top;
int dp[maxn],ind[maxn],col[maxn];
struct edge
{
int nxt,to;
}a[maxn],a1[maxn];
void add(int x,int y)
{
a[++cnt1].nxt=head[x];
head[x]=cnt1;
a[cnt1].to=y;
}
void add1(int x,int y)
{
a1[++cnt2].nxt=head1[x];
head1[x]=cnt2;
a1[cnt2].to=y;
}
void tarjan(int x)
{
dfsn[x]=low[x]=++tim;
stak[++top]=x;
for(int i=head[x];i;i=a[i].nxt)
{
int v=a[i].to;
if(!dfsn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(!col[v])//在栈里(被遍历过但是还没确定属于哪一个强连通分量)
{
low[x]=min(low[x],low[v]);
}
}
if(dfsn[x]==low[x])
{
col[x]=++cnt;//cnt记录强连通分量个数
sum[cnt]+=dis[x];
while(stak[top]!=x) sum[cnt]+=dis[stak[top]],col[stak[top--]]=cnt;//
//printf("%d\n",sum[cnt]);
top--;
}
return;
}
void topo()
{
queue<int> q;
for(int i=1;i<=cnt;i++)
if(!ind[i]) q.push(i);
while(!q.empty())
{
int now=q.front();q.pop();
for(int i=head1[now];i;i=a1[i].nxt)
{
int v=a1[i].to;
dp[v]=max(dp[v],dp[now]+sum[v]);
ind[v]--;
if(!ind[v]) q.push(v);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&dis[i]);
}
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)
{
if(!dfsn[i]) tarjan(i);
}
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=a[j].nxt)
{
v=a[j].to;
if(col[i]!=col[v])
{
add1(col[i],col[v]);
ind[col[v]]++;
}
}
topo();
int ans=0;
for(int i=1;i<=cnt;i++)
{
ans=max(ans,dp[i]);
// printf("%d\n",dp[i]);
}
printf("%d",ans);
return 0;
}