首页 > 代码库 > BZOJ 1093 最大半连通子图(强连通分量+树形DP)

BZOJ 1093 最大半连通子图(强连通分量+树形DP)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1093

题意:

思路:(1)首先,强连通分量中的一个点若在最大半连通子图中,则必定整个连通分量中的点都在,因为都在还是满足半连通的性质而且使得节点数更多。

(2)因此,求出强连通分量缩点,形成一个有向无环图,其实与树是差不多的。在这个图上DP一次即可,也就是找出最长链以及最长链的个数。

 

vector<int> g[N],g1[N];int n,m,mod;int dfn[N],low[N],visit[N],id;int c[N],cNum,p[N];int d[N];stack<int> st;void DFS(int u){    if(u)    {        low[u]=dfn[u]=++id;        st.push(u);    }    int i,v;    FOR0(i,SZ(g[u]))    {        v=g[u][i];        if(!dfn[v])        {            DFS(v);            low[u]=min(low[u],low[v]);        }        else if(!visit[v]) low[u]=min(low[u],dfn[v]);    }    if(!u) return;    if(low[u]==dfn[u])    {        cNum++;        do        {            v=st.top();            st.pop();            p[cNum]++;            c[v]=cNum;            visit[v]=1;        }while(u!=v);    }}set<int> S;int f[N],f1[N];pair<int,int> dfs(int u){    if(visit[u]) return MP(f[u],f1[u]);    if(SZ(g1[u])==0) return MP(p[u],1);    visit[u]=1;    int i,v;    pair<int,int> temp;    FOR0(i,SZ(g1[u]))    {        v=g1[u][i];        temp=dfs(v);        if(temp.first+p[u]>f[u])         {            f[u]=temp.first+p[u];            f1[u]=temp.second;        }        else if(temp.first+p[u]==f[u])        {            f1[u]=(f1[u]+temp.second)%mod;        }    }    return MP(f[u],f1[u]);}void deal(){    int i,j,v,x;    FOR1(i,n) FOR0(j,SZ(g[i]))    {        v=g[i][j];        if(c[i]!=c[v])        {            x=c[i]*(cNum+1)+c[v];            if(S.find(x)!=S.end()) continue;            S.insert(x);            d[c[v]]++;            g1[c[i]].pb(c[v]);        }    }    int Max=0,cnt=0;    pair<int,int> p;    clr(visit,0);    FOR1(i,cNum) if(!d[i])    {        p=dfs(i);        if(p.first>Max) Max=p.first,cnt=p.second;        else if(p.first==Max) cnt=(cnt+p.second)%mod;    }    PR(Max); PR(cnt);}int main(){    RD(n,m,mod);    int i,x,y;    FOR1(i,m) RD(x,y),g[x].pb(y);    FOR1(i,n) g[0].pb(i);    DFS(0); deal();}