bzoj1093【ZJOI2007】最大半联通子图

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1093

sol ：一开始理解错题意了QAQ，还莫名其妙写挂了QAQ，调了半天

　　　首先显然一个强联通分量肯定要么都属于最大半联通子图，要么都不属于

　　　所以先用tarjan缩点，重建后得到一个DAG

　　　之后我们可以发现，得到的答案一定是一条链，所以要求最长链的长度和数量

　　　直接dp即可，记得判重（我挂了好久QAQ）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mx=1000010;
int n,m,p,maxn,ans,cnt,tag,top;
int dfn[Mx],low[Mx],val[Mx],belong[Mx],stk[Mx];
int in[Mx],f[Mx],g[Mx],vis[Mx];
bool instk[Mx];
int tot,head1[Mx],head2[Mx],nxt1[2*Mx],ver1[2*Mx],nxt2[2*Mx],ver2[2*Mx];
void add1(int x,int y)
{
    nxt1[++tot]=head1[x];
    ver1[tot]=y;
    head1[x]=tot;
}
void add2(int x,int y)
{
    nxt2[++tot]=head2[x];
    ver2[tot]=y;
    head2[x]=tot;
    in[y]++;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    stk[++top]=x,instk[x]=1;
    for(int i=head1[x];i;i=nxt1[i])
    {
        int y=ver1[i];
        if(!dfn[y])
            tarjan(y),
            low[x]=min(low[x],low[y]);
        else if(instk[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        int now=0;tag++;
        while(now!=x)
        {
            now=stk[top--];
            instk[now]=0;
            val[tag]++;
            belong[now]=tag;
        }
    }
}
void rebuild()
{
    tot=0;
    for(int x=1;x<=n;x++)
        for(int i=head1[x];i;i=nxt1[i])
        {
            int y=ver1[i];
            if(belong[x]!=belong[y])
                add2(belong[x],belong[y]);
        }
}
void dp()
{
    int l=0,r=0;
    for(int i=1;i<=tag;i++)
    {
        if(!in[i]) stk[r++]=i;
        f[i]=val[i],g[i]=1;
    }
    while(l!=r)
    {
        int x=stk[l++];
        for(int i=head2[x];i;i=nxt2[i])
        {
            int y=ver2[i]; in[y]--;
            if(!in[y]) stk[r++]=y;
            if(vis[y]==x) continue;
            if(f[x]+val[y]>f[y])
            {
                f[y]=f[x]+val[y];
                g[y]=g[x];
            }
            else if(f[x]+val[y]==f[y])
                g[y]=(g[x]+g[y])%p;
            vis[y]=x;
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add1(x,y);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    rebuild(); dp();
    for(int i=1;i<=tag;i++)
    {
        if(f[i]>maxn) maxn=f[i],ans=g[i];
        else if(f[i]==maxn) ans+=g[i],ans%=p;
    }
    printf("%d
%d
",maxn,ans);
    return 0;
}

bzoj1093【ZJOI2007】最大半联通子图

相关推荐