题解 P2272 【[ZJOI2007]最大半连通子图】

· · 题解

我写这篇题解主要是为了两个trick：

1. Tarjan缩点后的点的排列顺序是逆拓扑序，所以不需要对新图进行拓扑排序

可以随机拍几组数据看一下

证明过程略

主要是我也不会

2. 拓扑序DP下的判重边：

只需要记录一下每一个点上一次是由谁转移而来的就好

如上，缩点后的代码就可以这样写：
（HEAD、VER、NEXT：新图的前向星；size：每个强
连通分量包含的点数；f：最大半连通子图的大
小；g：方案数）
    for(int x=scc;x>=1;x--) {                   //缩点后的顺序为逆拓扑序 
        for(int i=HEAD[x];i;i=NEXT[i]) {
            int y=VER[i];
            if(used[y]==x) continue;            //重边 
            used[y]=x;                  //记录转移 
            if(f[y]<f[x]+size[y]) {
                f[y]=f[x]+size[y];
                g[y]=g[x];
            }else if(f[y]==f[x]+size[y]) {
                g[y]+=g[x];
                g[y]%=MOD;
            }
        }
    }

附最终结果： 总用时：280ms

其他的就是常规的缩点和答案统计了

最后附上全部代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+2,M=2e6+2;
int n,m,tot,MOD,top,num,scc,TOT,Head[N],ver[M],Next[M],dfn[N],low[N],Stack[N],belong[N];
int size[N],HEAD[N],VER[M],NEXT[M],f[N],g[N],used[N];
bool instack[N];

inline int read() {
    int x=0;char y='*',z=getchar();
    while(z<'0'||z>'9') y=z,z=getchar();
    while(z>='0'&&z<='9') x=(x<<3)+(x<<1)+(z^48),z=getchar();
    return y=='-'?-x:x;
}
inline void add(int x,int y) {
    ver[++tot]=y;
    Next[tot]=Head[x];
    Head[x]=tot;
}
inline void ADD(int x,int y) {
    VER[++TOT]=y;
    NEXT[TOT]=HEAD[x];
    HEAD[x]=TOT;
}
inline void Tarjan(int x) {
    dfn[x]=low[x]=++num;
    Stack[++top]=x;
    instack[x]=true;
    for(int i=Head[x];i;i=Next[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(instack[y]) {
            low[x]=min(low[x],low[y]);
        }
    }
    if(dfn[x]==low[x]) {
        scc++;
        int k=-1;
        while(k!=x) {
            k=Stack[top--];
            belong[k]=scc;
            size[scc]++;
            instack[k]=false;
        }
    }
}
int main() {
//  freopen("test.txt","r",stdin);
    n=read();m=read();MOD=read();
    for(int i=1,x,y;i<=m;i++) {
        x=read(); y=read();
        add(x,y);
    }
    for(int i=1;i<=n;i++) {
        if(!dfn[i]) {
            Tarjan(i);
        }
    }
    for(int x=1;x<=n;x++) {
        f[x]=size[x];
        g[x]=1;
        for(int i=Head[x];i;i=Next[i]) {
            int y=ver[i];
            if(belong[x]==belong[y]) continue;
            ADD(belong[x],belong[y]);
        }
    }
    for(int x=scc;x>=1;x--) {                   //缩点后的顺序为逆拓扑序 
        for(int i=HEAD[x];i;i=NEXT[i]) {
            int y=VER[i];
            if(used[y]==x) continue;            //重边 
            used[y]=x;                          //记录转移 
            if(f[y]<f[x]+size[y]) {
                f[y]=f[x]+size[y];
                g[y]=g[x];
            }else if(f[y]==f[x]+size[y]) {
                g[y]+=g[x];
                g[y]%=MOD;
            }
        }
    }
    int ans=0,tmp=0;
    for(int i=1;i<=scc;i++) {
        if(f[i]>ans) {
            ans=f[i];
            tmp=g[i];
        }else if(f[i]==ans) {
            tmp+=g[i];
            tmp%=MOD;
        }
    }
    printf("%d\n%d",ans,tmp);
}