[ZJOI2007]最大半连通子图

题目

BZOJ

做法

弱联通子图，也就是本题的半联通子图
烂大街的概念：一个弱联通子图，一定是缩点后形成一条单直链
至此，我们将本题转化为\(DAG\)图上\(dp\)题，打完惊奇地发现\(WA\)了

本题坑点：\(DAG\)图上要去重操作，反正方案重复统计

My complete code

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef int LL;
const LL maxn=1e6;
struct node{
    LL to,nxt;
}dis[maxn];
LL num,tim,top,cnt,ansk,ansn,n,m,p;
LL head[maxn],dfn[maxn],low[maxn],du[maxn],sta[maxn],size[maxn],col[maxn],dp[maxn],sum[maxn];
bool visit[maxn];
inline void Add(LL u,LL v){
    dis[++num]=(node){v,head[u]}, head[u]=num;
}
void Tarjan(LL u){
    dfn[u]=low[u]=++tim; sta[++top]=u; visit[u]=true;
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(visit[v]) low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        LL now; ++cnt;
        do{
            now=sta[top--];
            col[now]=cnt;
            visit[now]=false;
            ++size[cnt];
        }while(now!=u);
    }
}
vector<LL> e[maxn];
inline void Solve(){
    queue<LL> que;
    for(LL i=1;i<=cnt;++i) 
        if(!du[i])
            que.push(i),dp[i]=size[i],sum[i]=1%p;
    while(que.size()){
        LL u(que.front()); que.pop();
        if(dp[u]>ansk){
            ansk=dp[u];
            ansn=sum[u];
        }else if(dp[u]==ansk) (ansn+=sum[u])%=p;
        for(LL i=0;i<e[u].size();++i){
            LL v(e[u][i]);
            if(!du[v]) continue;
            if(dp[u]+size[v]>dp[v]){
                dp[v]=dp[u]+size[v];
                sum[v]=sum[u];
            }else if(dp[u]+size[v]==dp[v])
                (sum[v]+=sum[u])%=p;
            --du[v];
            if(!du[v]) que.push(v);
        }
    }
}
struct E{
    LL u,v;
    bool operator < (const E &b)const{
        return (u^b.u)?u<b.u:v<b.v;
    }
}a[maxn];
int main(){
    cin>>n>>m>>p;
    for(LL i=1;i<=m;++i){
        LL u,v; cin>>u>>v;
        Add(u,v);
    }
    for(LL i=1;i<=n;++i)
        if(!dfn[i])
            Tarjan(i);
    num=0;
    for(LL u=1;u<=n;++u)
        for(LL i=head[u];i;i=dis[i].nxt){
            LL v(dis[i].to);
            if(col[v]!=col[u])
                a[++num]=(E){col[u],col[v]};
        }
    sort(a+1,a+1+num);
    a[0]=(E){-1,-1};
    for(LL i=1;i<=num;++i)
        if(a[i].u!=a[i-1].u || a[i].v!=a[i-1].v)
            e[a[i].u].push_back(a[i].v), ++du[a[i].v];
    Solve();
    cout<<ansk<<endl<<ansn;
    return 0;
}

[ZJOI2007]最大半连通子图

原文：https://www.cnblogs.com/y2823774827y/p/10470213.html