BZOJ
求仙人掌的直径(两点之间最短路径最大值)php
一开始看错题了,觉得是求仙人掌中的最长路径。。。
后来发现看错题了一下就改过来了。。ios
首先和普通的仙人掌\(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]))\)
发现维护一个单调队列,按照深度依次进栈,
这样子距离直接能够用深度作差,没有了绝对值
由于能够经过返祖边回去,所以把全部点按照顺序进两次队就能够了
第二次进队的时候给深度加上一个环大小再进队
而后如何保证是环上的最短路?
若是两个深度差已经大于环大小的一半了,那么最短路就不是这一条了
因此直接弹走队首就好了spa
#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; }