关于本题子图计数的疑惑

P2272 [ZJOI2007] 最大半连通子图

Jerrycyx @ 2024-07-25 20:34:18

代码如下：

//%%% stO Ronz Orz %%%
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

int quick_read()
{
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return x*w;
}

const int N=1e5+5,M=1e6+5;
int n,m,modX;
int ansK,ansC;
pair<int,int> save[M];

struct Allan{
    int to,nxt;
}raw_edge[M],scc_edge[M];
int raw_idx,raw_head[N];
inline void raw_add(int x,int y)
{
    raw_edge[++raw_idx]={y,raw_head[x]};
    raw_head[x]=raw_idx;
    return;
}
int scc_idx,scc_head[N];
inline void scc_add(int x,int y)
{
    scc_edge[++scc_idx]={y,scc_head[x]};
    scc_head[x]=scc_idx;
    return;
}

void InputData()
{
    n=quick_read(),m=quick_read(),modX=quick_read();
    for(int i=1;i<=m;i++)
    {
        save[i].first=quick_read(),save[i].second=quick_read();
        raw_add(save[i].first,save[i].second);
    }
    return;
}

int dfn[N],low[N],ti;
int sta[N],statop; bool insta[N];
int scc_belong[N],scc_size[N],scc_tot;
void Tarjan(int x)
{
    low[x]=dfn[x]=++ti;
    sta[++statop]=x,insta[x]=true;
    for(int i=raw_head[x];i;i=raw_edge[i].nxt)
    {
        int y=raw_edge[i].to;
        if(!dfn[y])
        {
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(insta[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        int tmp=0;
        scc_tot++;
        do
        {
            tmp=sta[statop];
            insta[tmp]=false,sta[statop--]=0;
            scc_belong[tmp]=scc_tot;
            scc_size[scc_tot]++;
        }while(tmp!=x);
    }
    return;
}

int scc_endeg[N];
void RebuildTree()
{
    for(int i=1;i<=m;i++)
    {
        save[i].first=scc_belong[save[i].first];
        save[i].second=scc_belong[save[i].second];
    }
    sort(save+1,save+m+1);
    for(int i=1;i<=m;i++)
    {
        if(save[i].first==save[i].second) continue;
        if(save[i].first!=save[i-1].first||save[i].second!=save[i-1].second)
        {
            scc_add(save[i].first,save[i].second);
            scc_endeg[save[i].second]++;
        }
    }
    return;
}

int maxlen[N],lencnt[N];
queue<int> top_q;
void TopSort()
{
    for(int i=1;i<=scc_tot;i++)
        if(!scc_endeg[i])
        {
            top_q.push(i);
            maxlen[i]=scc_size[i];
            lencnt[i]=1%modX;
        }
    while(!top_q.empty())
    {
        int x=top_q.front(); top_q.pop();
        for(int i=scc_head[x];i;i=scc_edge[i].nxt)
        {
            int y=scc_edge[i].to;
            if(maxlen[x]+scc_size[y]>maxlen[y])
            {
                maxlen[y]=maxlen[x]+scc_size[y];
                ansK=max(ansK,maxlen[y]);
                lencnt[y]=lencnt[x];//这里
            }
            if(maxlen[x]+scc_size[y]==maxlen[y])
                lencnt[y]=(lencnt[y]+lencnt[x])%modX;
            scc_endeg[y]--;
            if(!scc_endeg[y]) top_q.push(y);
        }
    }
    return;
}

void MainSolve()
{
    for(int i=1;i<=n;i++)
        if(!dfn[i]) Tarjan(i);
    RebuildTree();
    TopSort();
    return;
}

void OutputAns()
{
    for(int i=1;i<=scc_tot;i++)
        if(maxlen[i]==ansK) ansC=(ansC+lencnt[i])%modX;
    printf("%d\n%d\n",ansK,ansC);
    return;
}

int main()
{
    InputData();
    MainSolve();
    OutputAns();
    return 0;
}

在第 124 行中，lencnt[y]=lencnt[x]; 是错误的，而 lencnt[y]=0; 则正确，但是当更新到一个更大的链时，链的数量不应该更新成源链的数量吗？

并且在题解中写的也是 ans[edges[i].to]=ans[t] 而不是 0，我很不理解。

by Jerrycyx @ 2024-07-25 20:43:25

破案了，上面更新完 maxlen 后会立刻进入下方 == 的判断导致加两边.

by zengweijie123 @ 2024-07-25 20:47:09

代码如下:

//%%% stO Ronz Orz %%%
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

int quick_read()
{
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return x*w;
}

const int N=1e5+5,M=1e6+5;
int n,m,modX;
int ansK,ansC;
pair<int,int> save[M];

struct Allan{
    int to,nxt;
}raw_edge[M],scc_edge[M];
int raw_idx,raw_head[N];
inline void raw_add(int x,int y)
{
    raw_edge[++raw_idx]={y,raw_head[x]};
    raw_head[x]=raw_idx;
    return;
}
int scc_idx,scc_head[N];
inline void scc_add(int x,int y)
{
    scc_edge[++scc_idx]={y,scc_head[x]};
    scc_head[x]=scc_idx;
    return;
}

void InputData()
{
    n=quick_read(),m=quick_read(),modX=quick_read();
    for(int i=1;i<=m;i++)
    {
        save[i].first=quick_read(),save[i].second=quick_read();
        raw_add(save[i].first,save[i].second);
    }
    return;
}

int dfn[N],low[N],ti;
int sta[N],statop; bool insta[N];
int scc_belong[N],scc_size[N],scc_tot;
void Tarjan(int x)
{
    low[x]=dfn[x]=++ti;
    sta[++statop]=x,insta[x]=true;
    for(int i=raw_head[x];i;i=raw_edge[i].nxt)
    {
        int y=raw_edge[i].to;
        if(!dfn[y])
        {
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(insta[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        int tmp=0;
        scc_tot++;
        do
        {
            tmp=sta[statop];
            insta[tmp]=false,sta[statop--]=0;
            scc_belong[tmp]=scc_tot;
            scc_size[scc_tot]++;
        }while(tmp!=x);
    }
    return;
}

int scc_endeg[N];
void RebuildTree()
{
    for(int i=1;i<=m;i++)
    {
        save[i].first=scc_belong[save[i].first];
        save[i].second=scc_belong[save[i].second];
    }
    sort(save+1,save+m+1);
    for(int i=1;i<=m;i++)
    {
        if(save[i].first==save[i].second) continue;
        if(save[i].first!=save[i-1].first||save[i].second!=save[i-1].second)
        {
            scc_add(save[i].first,save[i].second);
            scc_endeg[save[i].second]++;
        }
    }
    return;
}

int maxlen[N],lencnt[N];
queue<int> top_q;
void TopSort()
{
    for(int i=1;i<=scc_tot;i++)
        if(!scc_endeg[i])
        {
            top_q.push(i);
            maxlen[i]=scc_size[i];
            lencnt[i]=1%modX;
        }
    while(!top_q.empty())
    {
        int x=top_q.front(); top_q.pop();
        for(int i=scc_head[x];i;i=scc_edge[i].nxt)
        {
            int y=scc_edge[i].to;
            if(maxlen[x]+scc_size[y]>maxlen[y])
            {
                maxlen[y]=maxlen[x]+scc_size[y];
                //这里修改了maxlen[y],让代码能进到下面的if 
                ansK=max(ansK,maxlen[y]);
                lencnt[y]=0; 
            }
            if(maxlen[x]+scc_size[y]==maxlen[y])//这个if 
                lencnt[y]=(lencnt[y]+lencnt[x])%modX;
                //如果上面写lencnt[y]=lencnt[x];会导致这里的重复计算 
            scc_endeg[y]--;
            if(!scc_endeg[y]) top_q.push(y);
        }
    }
    return;
}

void MainSolve()
{
    for(int i=1;i<=n;i++)
        if(!dfn[i]) Tarjan(i);
    RebuildTree();
    TopSort();
    return;
}

void OutputAns()
{
    for(int i=1;i<=scc_tot;i++)
        if(maxlen[i]==ansK) ansC=(ansC+lencnt[i])%modX;
    printf("%d\n%d\n",ansK,ansC);
    return;
}

int main()
{
    InputData();
    MainSolve();
    OutputAns();
    return 0;
}