【前情提要】贴主 @Rosmontis_ 由于被JC还在禁言中。
题目链接:P3387 【模板】缩点
全WA代码如下,求调:
#include<bits/stdc++.h>
using namespace std;
int maxn,n,m,a[10001],head[10001],cnt,dfn[10001],low[10001],col[10001],colt,st[10001],ztop,node[10001],zhead[10001],rd[10001],best[10001];
bool vis[10001];
struct edge
{
int v,next;
}e[100001],ze[100001];
inline int read()
{
int x=0,k=1;
char c=getchar();
while(c<'0'&&c>'9')
{
if(c=='-') k=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*k;
}
inline int mn(int x,int y)
{
return x<y ? x : y;
}
inline void add(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void zadd(int u,int v)
{
ze[++cnt].v=v;
ze[cnt].next=zhead[u];
zhead[u]=cnt;
}
void tarjan(int u)
{
st[++ztop]=u;
dfn[u]=low[u]=++cnt;
for(register int i=head[u];i;i=e[i].next)
{
if(!dfn[e[i].v])
{
tarjan(e[i].v);
low[u]=mn(low[u],low[e[i].v]);
}
if(!col[e[i].v]) low[u]=mn(low[u],low[e[i].v]);
}
if(dfn[u]==low[u])
{
col[u]=++colt;
while(st[ztop]!=u)
{
col[st[ztop]]=colt;
--ztop;
}
--ztop;
}
}
void topu(int u)
{
st[++ztop]=u;
while(ztop)
{
u=st[ztop--];
vis[u]=true;
for(register int i=zhead[u];i;i=ze[i].next)
{
best[ze[i].v]= best[ze[i].v] > best[u]+node[ze[i].v] ? best[ze[i].v] : best[u]+node[ze[i].v] ;
if(!(--rd[ze[i].v]))
st[++ztop]=ze[i].v;
}
}
}
int main()
{
n=read(); m=read();
for(register int i=1;i<=n;++i)
a[i]=read();
for(register int x,y,i=0;i<m;++i)
{
x=read(); y=read();
add(x,y);
} cnt=0;
for(register int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
cnt=0;
for(register int i=1;i<=n;++i)
{
node[col[i]]+=a[i];
for(register int j=head[i];j;j=e[j].next)
zadd(col[i],col[e[j].v]) , ++rd[col[e[j].v]];
}
for(register int i=1;i<=colt;++i) best[i]=node[i];
ztop=0;
for(register int i=1;i<=colt;++i)
if(!vis[i]&& !rd[i]) topu(i);
for(register int i=1;i<=colt;++i)
maxn = maxn>best[i] ? maxn : best[i];
cout<<maxn;
return 0;
}
注:可以过样例