$\texttt{\textcolor{red}{WA}}$ 60 Pts 求助

P2272 [ZJOI2007] 最大半连通子图

Jerrycyx @ 2022-05-29 10:46:26

\texttt{\textcolor{red}{WA}} 了最后三个点,都是第一行出错,代码如下:

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>

#define N 100005
#define M 1000005

using namespace std;

int n,m;
int x;

struct Allan{
    int from,to;
    int next;
}edge[M];
int tot=0;
int head[N];
int from[N],to[N];

int dfn[N],low[N];
int sta[N],top;
int num=0;
int scc[N],cnt=0;
int sum[N];

int deg[N];
int f[N],s[N];
int topcnt=0;

bool flag[N];
int d[N],a[N];
int out[N];
int ans1,ans2;

inline void add(int from,int to)
{
    tot++;
    edge[tot].from=from;
    edge[tot].to=to;
    edge[tot].next=head[from];
    head[from]=tot;
    deg[to]++;
    out[from]++;
    return;
}

inline void Get()
{
    scanf("%d%d%d",&n,&m,&x);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&from[i],&to[i]);
        add(from[i],to[i]);
    }
    return;
}

void Tarjan(int x)
{
    low[x]=dfn[x]=++num;
    sta[++top]=x;
    for(int i=head[x];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(dfn[to]==0)
        {
            Tarjan(to);
            low[x]=min(low[x],low[to]);
        }
        else if(scc[to]==0)
            low[x]=min(low[x],dfn[to]);
    }
    if(dfn[x]==low[x])
    {
        cnt++;
        while(sta[top+1]!=x)
        {
            scc[sta[top]]=cnt;
            sum[cnt]++;
            top--;
        }
    }
    return;
}
inline void Tarjan_All()
{
    for(int i=1;i<=n;i++)
        if(dfn[i]==0) Tarjan(i);
    return;
}

inline bool cmp(Allan x,Allan y)
{
    if(x.from==y.from) return x.to<y.to;
    else return x.from<y.from;
}

void Rebuild()
{
    for(int i=1;i<=m;i++)
    {
        edge[i].from=scc[edge[i].from];
        edge[i].to=scc[edge[i].to];
    }
    sort(edge+1,edge+m+1,cmp);
    memset(head,0,sizeof(head));
    memset(deg,0,sizeof(deg));
    memset(out,0,sizeof(out));
    tot=0;
    for(int i=1;i<=m;i++)
    {
        if(edge[i].from!=edge[i].to&&(edge[i].from!=edge[i-1].from||edge[i].to!=edge[i-1].to))
        {
            add(edge[i].from,edge[i].to);
        }
    }
    m=tot;
    return;
}

void Topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==0)
        {
            f[i]=sum[i];
            s[i]=1;
            ans1=max(ans1,f[i]);
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            deg[y]--;
            if(deg[y]==0)
                q.push(y);
            if(f[x]+sum[y]>f[y])
            {
                f[y]=f[x]+sum[y];
                ans1=max(ans1,f[y]);
                s[y]=0;
            }
            if(f[x]+sum[y]==f[y])
                s[y]=(s[y]+s[x])%(::x);
        }
    }
    return;
}

inline void Print()
{
    for(int i=1;i<=n;i++)
        if(f[i]==ans1)
            ans2=(ans2+s[i])%x;
    printf("%d\n%d\n",ans1,ans2);
    return;
}

int main()
{
    Get();
    Tarjan_All();
    Rebuild();
    Topsort();
    Print();
    return 0;
}

::x 代表访问全局变量 x


by TernaryTree @ 2022-05-29 10:48:22

标题别用 \LaTeX


|