P2272 [ZJOI2007]最大半连通子图

jiangchenyangsong · 2022-10-19 22:18:47 · 个人记录

哎，这道题打了半个小时，调了两个小时，最后发现竟然是把 Tarjan 里 while 给打成 if ,呜呜，枉费我两个小时时间，所以下次一定要记住不能打成 if （估计也就我一个人吧）

题意

定义最大半连通图：对于图中任意两点 u,v ,存在一条 u 到 v 的有向路径 或者 从 v 到 u 的有向路径。求一个图中不同的最大半连通子图的大小和数目。

分析

看到题目时应该很容易想到，如果两点互相可以到达，那么它们必是半连通图，所以考虑先 Tarjan 缩点，缩完点后，删去重边，图就成为 DAG,然后我们只要对这个图求一个最长链的长度和条数，就可以用拓扑进行 dp 了

设 dis_i 表示到 i 这个点的最长链长度， S_i 表示到 i 的最长链的条数， val_i 表示缩完点后，i 这个强连通分量的大小，很容易想到转移方程:

最后答案就是 ans1=max(dis_i) 和 ans2=\sum_{i=1}^{cnt}{S_i(dis_i==ans1)}.

一些小建议

#include<bits/stdc++.h>
#define N 1000005
#define M 10000005
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int n,m,mod,tot,t,cnt,dis[N],maxn,ss,top;
int dfn[N],low[N],s[N],vis[N],gp[N];
int Head[N],to[M],Next[M],val[N],S[N],pre[N];
map<pair<int,int>,bool> H;
void add(int u,int v){to[++tot]=v,pre[tot]=u,Next[tot]=Head[u],Head[u]=tot;}
void tarjan(int x){
    dfn[x]=low[x]=++t,vis[x]=1,s[++top]=x;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
        else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int k=s[top--];cnt++;
        while(x!=k){
            gp[k]=cnt,val[cnt]++,vis[k]=0;
            k=s[top--];
        }
        gp[x]=cnt,val[cnt]++,vis[x]=0,dis[cnt]=val[cnt],S[cnt]=1;
    }
}
int main(){
    n=read(),m=read(),mod=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();add(u,v);
    }
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    m=tot;
    tot=0,memset(Head,0,sizeof(Head));
    for(int i=1;i<=m;++i){
        int x=gp[pre[i]],y=gp[to[i]];
        if(x==y) continue;
        if(!H[make_pair(x,y)]) 
            add(x,y),H[make_pair(x,y)]=1;
    } 
    for(int x=cnt;x;--x){
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];
            if(dis[y]<dis[x]+val[y]) dis[y]=dis[x]+val[y],S[y]=S[x];
            else if(dis[y]==dis[x]+val[y]) S[y]=(S[y]+S[x])%mod; 
        }
    }
    for(int i=1;i<=cnt;++i){
        if(dis[i]>maxn) maxn=dis[i],ss=S[i];
        else if(dis[i]==maxn) ss+=S[i],ss%=mod;
    } 
    printf("%d\n%d\n",maxn,ss);
    return 0;
}