欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【BZOJ1023】仙人掌图(仙人掌,动态规划)

程序员文章站 2022-05-22 10:19:38
...

【BZOJ1023】仙人掌图(仙人掌,动态规划)

题面

BZOJ
求仙人掌的直径(两点之间最短路径最大值)

题解

一开始看错题了,以为是求仙人掌中的最长路径。。。
后来发现看错题了一下就改过来了。。

首先和普通的仙人掌\(dp\)是一样的,
对于没有问题的圆圆边,直接做最长链的转移(同时更新\(ans\)
然后对于一个环,把它拎出来单独考虑
首先要对于这个环,计算能够贡献的答案,
然后再用环上的值更新环的最顶点
先考虑怎么更新,这个直接拿环上的点的\(dp\)值,再计算一下这两点之间的最短路(深度差和环大小减深度差的较小值),相加去更新\(dp\)值。
然后考虑一下如何贡献答案,
要求的相当于是\(max(f[i]+f[j]+dist(i,j))\)
\(dist(i,j)=min(abs(dep[i]-dep[j]),circle\_size-abs(dep[i]-dep[j]))\)
发现维护一个单调队列,按照深度依次进栈,
这样子距离直接可以用深度做差,没有了绝对值
因为可以通过返祖边回去,因此把所有点按照顺序进两次队就可以了
第二次进队的时候给深度加上一个环大小再进队
然后如何保证是环上的最短路?
如果两个深度差已经大于环大小的一半了,那么最短路就不是这一条了
所以直接弹走队首就行了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 55555
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct Line{int v,next;}e[MAX<<3];
int h[MAX],cnt=1,n,m;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int f[MAX],ans=1,fa[MAX],dep[MAX],dfn[MAX],low[MAX],tim;
int H,T,Q1[MAX<<1],Q[MAX<<1];
void dp(int u,int y)
{
    int t=0;
    for(int i=y;i!=u;i=fa[i])Q1[++t]=i;Q1[++t]=u;
    reverse(&Q1[1],&Q1[t+1]);
    for(int i=1;i<=t;++i)Q1[i+t]=Q1[i];
    H=1;T=0;
    for(int i=1;i<=t+t;++i)
    {
        while(H<=T&&i-Q[H]>t/2)++H;
        if(H<=T)ans=max(ans,f[Q1[i]]+f[Q1[Q[H]]]+i-Q[H]);
        while(H<=T&&f[Q1[i]]-i>f[Q1[Q[T]]]-Q[T])--T;
        Q[++T]=i;
    }
    for(int i=y;i!=u;i=fa[i])
        f[u]=max(f[u],f[i]+min(dep[i]-dep[u],1+dep[y]-dep[i]));
}
void dfs(int u,int ff)
{
    fa[u]=ff;dfn[u]=low[u]=++tim;dep[u]=dep[ff]+1;
    for(int i=h[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(!dfn[v])dfs(v,u),low[u]=min(low[u],low[v]);
        else if(v!=ff)low[u]=min(low[u],dfn[v]);
        if(low[v]>dfn[u])
            ans=max(ans,f[u]+f[v]+1),f[u]=max(f[u],f[v]+1);
    }
    for(int i=h[u];i;i=e[i].next)
        if(fa[e[i].v]!=u&&dfn[u]<dfn[e[i].v])
            dp(u,e[i].v);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        int K=read(),a=read();
        for(int j=1;j<K;++j)
        {
            int b=read();
            Add(a,b);Add(b,a);
            a=b;
        }
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}