90 pts,RE #7,蹲个大佬来解答 代码如下(去掉头文件等不重要内容):
const ll N=5e5+10;
struct edge{
ll from,next,to,w;
}e[N],ex[N];
ll head[N],exhead[N],dfn[N],low[N],stark[N],ind[N];
ll point[N],dis[N],dist[N],color[N];
bool vis[N];
ll cnt,sum,n,m,ans,top,tot,cnt1;
void add(ll u,ll v)
{
e[++cnt].next=head[u];
e[cnt].from=u;
e[cnt].to=v;
//e[cnt].w=w;
head[u]=cnt;
}
void add_(ll u,ll v)
{
ex[++cnt1].next=exhead[u];
ex[cnt1].from=u;
ex[cnt1].to=v;
//e[cnt].w=w;
exhead[u]=cnt1;
}
void tarjan(ll u)
{
vis[u]=1;
dfn[u]=low[u]=++sum;
stark[++top]=u;
for(ll i=head[u];i;i=e[i].next)
{
ll v=e[i].to;
if(!vis[v]) {tarjan(v);low[u]=min(low[u],low[v]);}
if(vis[v])
{
low[u]=min(low[u],low[v]);
}
}
//cout<<1<<"\n";
if(dfn[u]==low[u])
{
tot++; ll y=stark[top];
while(1)
{
y=stark[top--];
color[y]=tot;
vis[y]=0;
dis[tot]+=point[y];
if(y==u) break;
}
}
}
void spfa()
{
//cout<<1<<endl;
ll sum=0;
memset(dist,-0x3f,sizeof(dist));
memset(vis,false,sizeof(vis));
queue<ll> q;
for(ll i=1;i<=tot;++i) {
if(ind[i]==0) {
q.push(i);
vis[i]=1;
dist[i]=dis[i];
}
}
//q.push(x);
//vis[x]=true;dist[x]=0;
while(!q.empty())
{
ll x;
x=q.front();q.pop();
vis[x]=false;
sum=max(sum,dist[x]+dis[x]);
for(ll i=exhead[x];i;i=ex[i].next)
{
ll y=ex[i].to;
if(dist[y]<dist[x]+dis[y])
dist[y]=dist[x]+dis[y];// 更新
if(vis[y]) continue;
q.push(y);
}
}
return ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("q.in","r",stdin);
freopen("q.out","w",stdout);
#endif
n=read();m=read();
for(ll i=1;i<=n;++i) point[i]=read();
for(ll i=1,u,v;i<=m;++i)
{
u=read(); v=read();
add(u,v);
}
//cout<<1<<endl;
for(ll i=1;i<=n;++i)
{
if(dfn[i]==0) tarjan(i);
}
//cout<<1<<endl;
for(ll i=1;i<=n;++i)
{
for(ll j=head[i];j;j=e[j].next)
{
if(color[i]!=color[e[j].to]) {
add_(color[i],color[e[j].to]);
ind[color[e[j].to]]++;
}
}
}
//cout<<1<<endl;
spfa();ans=-1;
for(ll i=1;i<=tot;++i)
{
ans=max(ans,dist[i]);
}
printf("%d",ans);
return 0;
}