【bzoj1023】[SHOI2008]cactus仙人掌图

2015.04.25 11:37 Sat | 2次阅读 | 旧日oi | 固定链接 | 源码

Description

如果某个无向连通图的任意一条边至多只出现在一条简单回路(simple cycle)里,我们就称这张图为仙人图(cactus)。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

举例来说,上面的第一个例子是一张仙人图,而第二个不是——注意到它有三条简单回路:(4,3,2,1,6,5,4)、(7,8,9,10,2,3,7)以及(4,3,7,8,9,10,2,1,6,5,4),而(2,3)同时出现在前两个的简单回路里。另外,第三张图也不是仙人图,因为它并不是连通图。显然,仙人图上的每条边,或者是这张仙人图的桥(bridge),或者在且仅在一个简单回路里,两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1,你的任务是求出给定的仙人图的直径。

Input

输入的第一行包括两个整数n和m(1≤n≤50000以及0≤m≤10000)。其中n代表顶点个数,我们约定图中的顶点将从1到n编号。接下来一共有m行。代表m条路径。每行的开始有一个整数k(2≤k≤1000),代表在这条路径上的顶点个数。接下来是k个1到n之间的整数,分别对应了一个顶点,相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次,比如对于第一个样例,第一条路径从3经过8,又从8返回到了3,但是我们保证所有的边都会出现在某条路径上,而且不会重复出现在两条路径上,或者在一条路径上出现两次。

Output

只需输出一个数,这个数表示仙人图的直径长度。

Sample Input

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10 8
10 1
10 1 2 3 4 5 6 7 8 9 10

Sample Output

9

HINT

对第一个样例的说明:如图,6号点和12号点的最短路径长度为8,所以这张图的直径为8。

【注意】使用Pascal语言的选手请注意:你的程序在处理大数据的时候可能会出现栈溢出。如果需要调整栈空间的大小,可以在程序的开头填加一句:{$M 5000000},其中5000000即指代栈空间的大小,请根据自己的程序选择适当的数值。

题解

传说中的仙人掌!
大概的做法:
用f[i]表示i到i的子树的最长路,如果i位于一个环,那么不考虑环上的边。将f[i]的最大值和次大值相加可以用来更新答案,这部分是类似树上两个点的lca
然后是环,我们把搜索时第一个搜到的点u设为环的最高点,则f[u]可以用f[v]+min(tot,size-tot)更新,v是环上的其它节点,size是环的大小,tot是扫描的编号。
然后我们还有如下更新ans=max(ans,f[v1]+f[v2]+dis(v1,v2)),就是环上的两个节点的f值加上这两个点的距离,这部分可以用一个单调队列环型DP维护
另:此题用vector存边会wa

我的程序

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m,ans,tot;
int low[maxn],dfn[maxn];
int a[maxn],fa[maxn],f[maxn];
struct Que
{
    int w,p;
}q[maxn];
struct edge
{
    int to,next;
}e[2222222];
int h[maxn],tp;
void ae(int u,int v)
{
    e[++tp].to=v;e[tp].next=h[u];h[u]=tp;
}
void update()
{
    int h=1,t=1;
    for(int i=1;i<=tot;i++) a[tot+i]=a[i];
    for(int i=1;i<=(tot<<1);i++)
    {
        while(h<t&&i-q[h].p>(tot>>1)) h++;
        while(h<t&&q[t].w<=f[a[i]]-i) t--;
        q[++t].p=i; q[t].w=f[a[i]]-i;
        ans=max(ans,f[a[i]]+i+q[h].w);
    }
}
void tarjan(int u)
{
    low[u]=dfn[u];
    for(int i=h[u];e[i].to;i=e[i].next)
    {
        int v=e[i].to;
        if(fa[v]!=0&&v!=fa[u]) low[u]=min(low[u],dfn[v]);
        if(fa[v]==0)
        {
            fa[v]=u; dfn[v]=dfn[u]+1; tarjan(v);
            low[u]=min(low[u],low[v]);
        }
    }
    for(int i=h[u];e[i].to;i=e[i].next)
    {
        int v=e[i].to;
        if(fa[v]==u&&low[v]>dfn[u])
        {
            ans=max(ans,f[v]+1+f[u]);
            f[u]=max(f[u],f[v]+1);
        }
        if(fa[v]!=u&&dfn[u]<dfn[v])
        {
            int x=v; tot=0;
            while(x!=fa[u]) a[++tot]=x,x=fa[x];
            update();
            for(int j=1;j<tot;j++) f[u]=max(f[u],f[a[j]]+min(j,tot-j));
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int k,x,t,i=1;i<=m;i++)
    {
        scanf("%d%d",&k,&t);
        for(int j=2;j<=k;j++)
        {
            scanf("%d",&x);
            ae(x,t);ae(t,x);
            t=x;
        }
    }
    fa[1]=-1;
    tarjan(1);
    printf("%d\n",ans);
}```