题解 P1399 【[NOI2013]快餐店】

· · 题解

贴个博客链接

首先我们要知道，如果是树的话，重心的位置一定在一半的直径里那个位置对吧。

所以如果图是一棵树，那么1/2的直径长就是答案了。

（然而这道题没有树的部分分）

看到有n条边就知道是基环树。

既然是基环树，那么我们就应该把环作为重点研究对象。

环就是解题的关键，习惯性地把基环树画成细菌

此时这个基环树的直径有两种情况 有经过基环 或 没有经过基环

没有经过基环的就是环上挂着的每一棵小子树的最大直径了。

有经过基环的怎么求呢？

考虑枚举每个位置把环断开（基环树常见套路）。

对每一个子树求一个最大深度，然后Max(两个子树最大深度加它们在环上的距离)就为直径了。

但我们有很多种断环方案，每一次都求一次复杂度肯定是要上天的。

所以想个办法优化（这里借鉴了ljh2000的方法）

先在1到tot（环长）的地方断开。

pre[]与bck[]分别表示前缀和后缀的 Max[某个子树最大深度+它的前缀（后缀）链长]

bs1[]和bs2[]分别表示前缀和后缀的 Max[某两个子树的最大深度+它们之间的距离]

所以每次从i到i+1的地方断开，答案的求法就很简单了。

For(i,1,tot-1){
    Db mx1=max(bs1[i],bs2[i+1]);
    Db mx2=max(mx1,pre[i]+bck[i+1]+crD[0]);
    Fn=min(Fn,max(mx1,mx2));
}

DFS抠环、断环的时候比较繁琐一定要注意细节。

好了上代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>

#define For(i,a,b) for(register int i=a;i<=b;++i)
#define Dwn(i,a,b) for(register int i=a;i>=b;--i)
#define Pn putchar('\n')
#define Re register
#define Db double

using namespace std;

const int N=1e5+5;

int head[N],nxt[N*2],v[N*2],cnt=1;
Db w[N*2],dia[N],z,dmx[N],Fn;
int n,m,x,y;
inline void read(int &v){
    v=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
}
inline void read(Db &v){
    v=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
}
void add(int ux,int vx,Db wx){
    nxt[++cnt]=head[ux]; head[ux]=cnt; v[cnt]=vx; w[cnt]=wx;
    nxt[++cnt]=head[vx]; head[vx]=cnt; v[cnt]=ux; w[cnt]=wx;
}

int tot=0,top=0,st[N],cr[N*2],vis[N],suc=0,fc[N];
Db crD[N*2],stD[N];
void dfsCir(int x,int fa){
    vis[x]=1;
    if(x==1)st[++top]=x,stD[top]=0;
    for(Re int i=head[x];i;i=nxt[i]){
        int vv=v[i]; if(vv==fa)continue;
        if(!vis[vv]){
            st[++top]=vv; stD[top]=w[i];
            dfsCir(vv,x);
        }else{
            suc=1;
            while(st[top]!=vv){
                fc[st[top]]=1;
                cr[++tot]=st[top];
                crD[tot]=stD[top--];
            }
            fc[st[top]]=1;
            cr[++tot]=st[top];
            crD[tot]=w[i];
            return;
        }
        if(suc)return;
    }
    top--;
}
int pos;
Db mxD;
void dfsTrD(int x,Db dix,int fa){
    if(dix>mxD)mxD=dix,pos=x;
    for(Re int i=head[x];i;i=nxt[i]){
        int vv=v[i];
        if(vv==fa||fc[vv])continue;
        dfsTrD(vv,dix+w[i],x);
    }
}
Db GetTrD(int x){
    pos=mxD=0;
    dfsTrD(x,0,0);
    mxD=0;
    dfsTrD(pos,0,0);
    return mxD;
}

Db pre[N],bck[N],bs1[N],bs2[N],Ds=0; 
void DP(){
    Ds=mxD=0;
    For(i,1,tot){
        pre[i]=max(pre[i-1],dmx[cr[i]]+Ds);
        if(i>=2)bs1[i]=max(bs1[i-1],mxD+Ds+dmx[cr[i]]);
        mxD=max(mxD,dmx[cr[i]]-Ds);
        Ds+=crD[i];
    }
    Ds=mxD=0;
    crD[0]=crD[tot];
    Dwn(i,tot,1){
        bck[i]=max(bck[i+1],dmx[cr[i]]+Ds);
        if(i<=tot-1)bs2[i]=max(bs2[i+1],mxD+Ds+dmx[cr[i]]);
        mxD=max(mxD,dmx[cr[i]]-Ds);
        Ds+=crD[i-1];
    }
    Fn=bs1[tot];
    For(i,1,tot-1){
        Db mx1=max(bs1[i],bs2[i+1]);
        Db mx2=max(mx1,pre[i]+bck[i+1]+crD[0]);
        Fn=min(Fn,max(mx1,mx2));
    }
}

int main(){
    //freopen("ex.in","r",stdin);
//  freopen("ex.out","w",stdout);
    read(n); 
    For(i,1,n){read(x); read(y); read(z); add(x,y,z);}
    dfsCir(1,0); 
    For(i,1,tot){
        fc[cr[i]]=0;
        dia[cr[i]]=GetTrD(cr[i]);
        fc[cr[i]]=1;
    }
    For(i,1,tot){
        mxD=0; 
        dfsTrD(cr[i],0,0);
        dmx[cr[i]]=mxD;
    } 
    DP();
    For(i,1,tot)Fn=max(Fn,dia[cr[i]]);
    printf("%.1lf",Fn/2.0);
    return 0;
}