社区讨论

【代人发帖】tarjan缩点全WA求助QwQ

学术版参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lobgzjry
此快照首次捕获于
2023/10/29 20:51
2 年前
此快照最后确认于
2023/11/04 02:11
2 年前
查看原帖
【前情提要】贴主 @Rosmontis_ 由于被JC还在禁言中。
题目链接:P3387 【模板】缩点
全WA代码如下,求调:
CPP
#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;
}
注:可以过样例

回复

5 条回复,欢迎继续交流。

正在加载回复...