洛谷 P2272/bzoj 1093 [ZJOI2007]最大半连通子图 题解【tarjan】【贪心】【树形DP】

点击量：192

    一个比较难想的贪心+方案统计顺带树形DP。

目录

题目描述

一个有向图$ G=(V,E)$称为半连通的(Semi-Connected)，如果对于：$ \forall u,v\in V$，满足$ u\rightarrow v$或$ v\rightarrow u$，即对于图中任意两点$ u,v$,存在一条$ u$到$ v$的有向路径或者从$ v$到$ u$的有向路径。若$ G’=(V’,E’)$满足$ V’\in V$，$ E’$是$ E$中所有跟$ V’$有关的边，则称$ G’$是$ G$的一个导出子图。若$ G’$是$ G$的导出子图，且$ G’$半连通，则称$ G’$为$ G$的半连通子图。若$ G’$是$ G$所有半连通子图中包含节点数最多的，则称$ G’$是$ G$的最大半连通子图。给定一个有向图$ G$，请求出$ G$的最大半连通子图拥有的节点数$ K$，以及不同的最大半连通子图的数目$ C$。由于$ C$可能比较大，仅要求输出$ C$对$ X$的余数。

 

输入输出格式

输入格式：

第一行包含两个整数$ N,M,X$。$ N,M$分别表示图$ G$的点数与边数，X的意义如上文所述接下来M行，每行两个正整数$ a,b$，表示一条有向边$ (a, b)$。图中的每个点将编号为$ 1,2,3…N$，保证输入中同一个$ (a,b)$不会出现两次。

 

输出格式：

应包含两行，第一行包含一个整数$ K$。第二行包含整数$ C \mod X$.

 

输入输出样例

输入样例#1：

6 6 20070603

1 2

2 1

1 3

2 4

5 6

6 4

输出样例#1：

3

3

说明

对于100%的数据，$ N \le 100000, M \le 1000000, X \le 10^8$

题解：

    对于最大半连通子图，如果满足任意两点之间都有关系，那么多画几个图，发现它不能有平行的边，也就是两点间路径唯一，可以是一棵有向树。不过对于任意两点，树就不满足这个性质，因此最大半连通子图有链的性质。同样可以发现，这里的环是可以被看作一个点的。环上的点能互相到达，因此环上的任一点都能通过环走到环上其他点的外向边去。因此，可以把一个大小为$ k$的环缩为一个权值为$ k$的点。这一点tarjan强连通分量缩点就可以完成。

    接着求出最长链，这里可以用记忆化搜索+树形DP来实现。枚举每个没有被做过的点，进行DFS。每个点自身的方案数为1，如果它被多条最长路更新，那它的方案就是多条最长路方案之和。每次找到最长链更新答案，相同的最长链累加就可以了。

    学会了tarjan缩点后对边的处理:在前向星中额外加入变量from，表示该边的起点。以from为第一关键字，n为第二关键字排序，然后unique去重。将ecnt更新到当前边数，重置head数组，把这些边按from和n重新相连即可。这个题要注意自环是有影响的，重边要消除。因为重边和自环虽然不会导致最长链持续更新下去，但是会更新方案数。根据子图的定义，它是由点集唯一确定的，因此下图中编号为1和2的边也只能算一种方案，因为点集$ {1,2}$被唯一确定。

    因此在记忆化搜索过程中记下方案数，每次更新时先改变答案，再更新答案有关的方案数就完成了。记得mod p。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
int min(int x,int y)
{
    return x<y?x:y;
}
int max(int x,int y)
{
    return x>y?x:y;
}
struct edge
{
    int from,n,nxt;
    edge(int from,int n,int nxt)
    {
        this->from=from;
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
    friend bool operator <(edge a,edge b)
    {
        if(a.from!=b.from)
            return a.from<b.from;
        return a.n<b.n;
    }
    friend bool operator ==(edge a,edge b)
    {
        return a.from==b.from&&a.n==b.n;
    }
}e[1010000];
int head[101000],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(from,to,head[from]);
    head[from]=ecnt;
}
int w[101000];
int dfn[101000],low[101000],cnt=0;
int del[101000],in[101000],stk[101000],top=0;
void tarjan(int x)
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    in[x]=1;
    stk[++top]=x;
    for(int i=head[x];~i;i=e[i].nxt)
    {
        if(dfn[e[i].n]&&!in[e[i].n])
            continue;
        if(dfn[e[i].n])
            low[x]=min(low[x],dfn[e[i].n]);
        else
        {
            tarjan(e[i].n);
            low[x]=min(low[x],low[e[i].n]);
        }
    }
    if(dfn[x]==low[x])
    {
        int cntt=0;
        do
        {
            cntt++;
            in[stk[top]]=0;
            del[stk[top--]]=x;
        }while(stk[top+1]!=x);
        w[x]=cntt;
    }

}
int p;
int used[101000];
int ans=0,acnt=0;
int f[101000];
void dfs(int x)
{
    int tmp=0;
    for(int i=head[x];~i;i=e[i].nxt)
    {
        if(!used[e[i].n])
        {
            used[e[i].n]=1;
            dfs(e[i].n);
        }
        if(ans==w[x]+w[e[i].n])
            acnt+=f[e[i].n];
        if(ans<w[x]+w[e[i].n])
        {
            ans=w[x]+w[e[i].n];
            acnt=f[e[i].n];
        }

        if(tmp==w[e[i].n])
            f[x]+=f[e[i].n];
        if(tmp<w[e[i].n])
        {
            tmp=w[e[i].n];
            f[x]=f[e[i].n];
        }
    }
    if(ans==w[x])
        acnt++;
    if(ans<w[x])
    {
        ans=w[x];
        acnt=1;
    }
    w[x]+=tmp;
    f[x]%=p;
    acnt%=p;
}
int main()
{
    int n,m;
    scanf("%d%d%d",&n,&m,&p);
    memset(head,-1,sizeof(head));
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=head[i];~j;j=e[j].nxt)//删边过程
        {
            e[j].n=del[e[j].n];
            e[j].from=del[i];
        }
    std::sort(e,e+1+ecnt);
    std::unique(e,e+1+ecnt);
    for(int i=1;i<=ecnt;i++)
        if(e[i].from<e[i-1].from||(e[i].from==e[i-1].from&&e[i].n<=e[i-1].n))
        {
            ecnt=i-1;
            break;
        }
    memset(head,-1,sizeof(head));
    for(int i=0;i<=ecnt;i++)
    {
        if(e[i].from==e[i].n)
            continue;
        e[i].nxt=head[e[i].from];
        head[e[i].from]=i;
    }
    for(int i=1;i<=n;i++)
        f[i]=1;
    for(int i=1;i<=n;i++)
        if(del[i]==i&&!used[i])
        {
            used[del[i]]=1;
            dfs(del[i]);
        }
    printf("%d\n",ans);
    printf("%d\n",acnt%p);
    return 0;
}