bzoj1023【SHOI2008】cactus仙人掌图

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1023

　　　求一棵仙人掌的直径

sol ：orz YDC神犇 http://ydcydcy1.blog.163.com/blog/static/21608904020131493113160/

　　 orz z55250825神犇 http://z55250825.blog.163.com/blog/static/150230809201412793151890/

　　对于一棵仙人掌，只有两种边：环上的边以及割边(桥)，这两种边需要分开讨论

　　先进行一遍dfs，得到一棵dfs树，然后考虑树形dp

　　定义f[i]表示在dfs树上，以i为根的子树且在i的诱导子图中以i为起点的最长链

　　 P.S.诱导子图定义：G'=(V', E')，V'⊆V，E'={ (u, v) | u, v∈V'，(u, v)∈E }，则G'为G的诱导子图。

　　先考虑没有环的情况，对于最远点对所在的路径，一定有以下性质：

　　　　该路径必定存在一个节点，它在这条路径上的所有点中深度最小（这个易证）

　　所以，f[u]的转移方程为，f[u]=max(f[v]+1)，答案即为最长的儿子+次长的儿子+2

　　考虑非树边，显然一条非树边会形成一个环，对于环上各点，其实是地位平等的，所以可以将环上信息放在最高点上并向上传递即可

　　考虑环会带来什么影响

　　　　对于点u及其儿子v，如果二者在同一个环上，且u不是最高点，则不用更新答案，直接跳过，搜索其他点

　　　　这是因为除最高点以外的点的f值只会影响到环上点的f值，而不会影响其他环的f值

　　　　跳过后可以看出，节点u的f值只储存了与不在同一个环上的点的最长路径，然后对环上的点进行更新

　　　　环上的点更新的原理我不是太明白，所以直接拷贝dalao的博客了QAQ

　　　　所以最后就是，对于环上的点u,v，用dis(u,v)+f[v]来更新f[u]即可

　　　　可以用单调队列维护，由于是环，将链长翻倍即可

　　　　如果是最高点的话，直接枚举一边计算即可

　　所以算法的流程就是，先tarjan判环，然后如果是桥就直接更新，否则把所有点取出然后dp这个环即可

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

const int Mx1=;

const int Mx2=;

int n,m,l,r,cnt,ans,dep[Mx1],f[Mx1],fa[Mx1],dfn[Mx1],low[Mx1];

int tot,head[Mx1],nxt[Mx2],ver[Mx2],a[*Mx1],q[*Mx1];

inline void add(int x,int y)

{

    nxt[++tot]=head[x];

    ver[tot]=y;

    head[x]=tot;

}

void Dp(int root,int x)

{

    tot=dep[x]-dep[root]+;

    for(int i=x;i!=root;i=fa[i]) a[tot--]=f[i];

    a[tot]=f[root];

    tot=dep[x]-dep[root]+;

    for(int i=;i<=tot;i++) a[i+tot]=a[i];

    q[]=l=r=;

    for(int i=;i<=*tot;i++)

    {

        while(l<=r&&i-q[l]>tot/) l++;

        ans=max(ans,a[i]+i+a[q[l]]-q[l]);

        while(l<=r&&a[q[r]]-q[r]<=a[i]-i) r--;

        q[++r]=i;

    }

    for(int i=;i<=tot;i++)

        f[root]=max(f[root],a[i]+min(i-,tot-i+));

}

void Dfs(int x)

{

    low[x]=dfn[x]=++cnt;

    for(int i=head[x];i;i=nxt[i])

    {

        int y=ver[i];

        if(y!=fa[x])

        {

            if(!dfn[y])

            {

                fa[y]=x,dep[y]=dep[x]+;

                Dfs(y);

                low[x]=min(low[x],low[y]);

            }

            else low[x]=min(low[x],dfn[y]);

            if(dfn[x]<low[y])

            {

                ans=max(ans,f[x]+f[y]+);

                f[x]=max(f[x],f[y]+);

            }

        }

    }

    for(int i=head[x];i;i=nxt[i])

    {

        int y=ver[i];

        if(fa[y]!=x&&dfn[x]<dfn[y]) Dp(x,y);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    while(m--)

    {

        int k,a,b;scanf("%d",&k);

        for(int i=;i<=k;i++)

        {

            scanf("%d",&b);

            if(i!=) add(a,b),add(b,a);

            a=b;

        }

    }

    Dfs();

    printf("%d\n",ans);

    return ;

}

巴特西

bzoj1023【SHOI2008】cactus仙人掌图

最新文章

热门文章