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

作者: wjyyy 分类: tarjan,搜索,树形DP,解题报告,记忆化搜索,贪心 发布时间: 2018-07-25 22:07

点击量:18

 

    一个比较难想的贪心+方案统计顺带树形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;
}

说点什么

avatar
  Subscribe  
提醒
/* */