[BZOJ1023][SHOI2008][仙人掌直径][队列优化DP]cactus仙人掌图

求仙人掌直径裸题 看这篇题解吧 http://z55250825.blog.163.com/blog/static/150230809201412793151890/

#include <cstdio> #include <iostream> #include <algorithm> #define N 100010 using namespace std; int n,m,u,v,k,cnt,Ans,tms; int G[N],dpt[N],f[N],dfn[N],low[N],fa[N],a[N],q[N]; struct edge{ int t,nx; }E[20000010]; inline void reaD(int &x){ char c=getchar(); x=0; for(;c>57||c<48;c=getchar());for(;c>=48&&c<=57;x=x*10+c-48,c=getchar()); } inline void Insert(int x,int y){ E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt; E[++cnt].t=x; E[cnt].nx=G[y]; G[y]=cnt; } inline void dp(int x,int y){ int deep=dpt[y]-dpt[x]+1; for(int i=y;i!=x;i=fa[i]) a[deep--]=f[i]; a[deep]=f[x]; deep=dpt[y]-dpt[x]+1; for(int i=1;i<=deep;i++) a[i+deep]=a[i]; int l=1,r=0; for(int i=1;i<=2*deep;i++){ while(l<=r&&i-q[l]>deep/2) l++; if(l<=r) 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=2;i<=deep;i++) f[x]=max(f[x],a[i]+min(i-1,deep-i+1)); } void dfs(int x,int p){ dfn[x]=low[x]=++tms; dpt[x]=dpt[p]+1; fa[x]=p; for(int i=G[x];i;i=E[i].nx) if(E[i].t!=p){ if(!dfn[E[i].t]) dfs(E[i].t,x); low[x]=min(low[x],low[E[i].t]); if(low[E[i].t]>dfn[x]){ Ans=max(Ans,f[x]+f[E[i].t]+1); f[x]=max(f[x],f[E[i].t]+1); } } for(int i=G[x];i;i=E[i].nx) if(x!=fa[E[i].t]&&dfn[x]<dfn[E[i].t]) dp(x,E[i].t); } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); reaD(n); reaD(m); for(int i=1;i<=m;i++){ reaD(k); reaD(u); for(int j=2;j<=k;j++) reaD(v),Insert(u,v),u=v; } dfs(1,0); PRintf("%d\n",Ans); }