题解 P1399 【[NOI2013]快餐店】

· · 题解

算法分析：

首先这是一道基环树的题。给定 n 个点和 n 条边，而且保证联通，那么就存在一个环。

要求出一个点到离它距离最远的点的距离最小，显然跟直径有关，求出此基环树的直径，答案为直径除以 2。

那么考虑如何求直径。有两种情况。

$2$.直径经过基环。 在求直径之前，我们需要将哪些点在环上记录下来。我们从 $1$ 号点开始深搜找环。具体看代码注释。 ```cpp inline bool find(int u){ vis[u] = 1; //这个点记录为走过 for(re int i(head[u]) ; i ; i=e[i].nxt){ int v = e[i].to; if(v == fa[u]) continue; //走到了父亲不行 fa[v] = u; w[v] = e[i].w; //将这条边的边权转化为儿子的点权，和树剖的转化类似 if(!vis[v]) { if(find(v)) return 1; } //如果这个点没有走过而且后面能找到环，就一直往回return else{ //找到了环 int p = u; //枚举环上的点 while(1){ inc[p] = 1; //inc[p]=1表示p在环上 cv[++tot] = p; //环上的点的编号，由于后面操作，我们需要重新编号 cw[tot] = w[p]; //环上这个编号点的点权 p = fa[p]; //由于记录了fa[p]是p的父亲，所以可以往回找 if(p == u) break; //环遍历完了 } return 1; //记录已经找到环 } } return 0; //没找到就继续往下找 } ``` 一个一个考虑，先看直径不经过基环，这个比较好求。此基环树的直径为环上挂着的点的每一棵子树的最大直径，记为 $res1$，枚举环上的每一个点，深搜计算子树的直径 $res1 = max(d[u]+d[v]+w(u,v))$。顺道求出以 $u$ 为根的子树的最大深度 $d[u]$。 ```cpp inline void dfs(int u,int fa){ for(re int i(head[u]) ; i ; i=e[i].nxt){ int v = e[i].to,w = e[i].w; if(inc[v] || v==fa) continue; //如果这个点在环上，或者搜到了父亲就不继续 dfs(v,u); //往下搜 res1 = max(res1,d[u]+d[v]+w); //求最大的直径 d[u] = max(d[u],d[v]+w); //顺道记录下来以u为根的最大深度 } } rep(i,1,tot) dfs(cv[i],0); ``` 然后来看直径经过环。一个最简单的想法就是，暴力枚举删哪一条边， $res[i] = max ($两个子树的深度 $+$ 它们在环上的距离 $)$。则经过环的直径 $res2 = min(res[i])$。 但这样做复杂度是 $n^2$ 的，过不去本题。考虑如何进行优化。 $1$.把边 $(1,tot)$ 断开，$tot$ 为环上有 $tot$ 个点，预处理前缀长度。 $A[i] = max($ 前缀中链的长度 $+$ 节点树的深度 $)$。 $B[i] = max($ 前缀中两棵树的深度 $+$ 这两个节点之间的距离 $)$。 $2$.把边 $(1,tot)$ 断开，预处理后缀长度。 $C[i] = max($ 后缀中链的长度 $+$ 节点树的深度 $)$。 $D[i] = max($ 后缀中两棵树的深度 $+$ 这两个节点之间的距离 $)$。 3.枚举断开环上的边 $(i,i+1)$，拼凑答案。 $res[i] = max(B[i],D[i+1],A[i]+C[i+1]+w(1,tot))

则经过环的直径 res2 = min(res[i])。

注意，最后需要有个特判，断开 (1,tot) 这条边，需要加上一句话 res2 = min(res2,B[tot])。

那么基环树的直径就是 max(res1,res2)，这道题的答案就是 max(res1,res2)/2。

double sum=0,mx=0;
    rep(i,1,tot){ //预处理前缀 
        sum += cw[i-1]; //sum就是链长的加和 
        A[i] = max(A[i-1],sum+d[cv[i]]); //根据A数组的定义来推 
        B[i] = max(B[i-1],mx+d[cv[i]]+sum); //这里很巧妙
                                            //我们的mx记录的是i这个点之前的某一个点k的深度-k之前的链长 
                                            //也就是说，我们要求B数组，可以用一个抵消的思想
                                            //sum记录的是链长的加和，再加上mx，也就把k前面的链长消掉了
                                            //最后剩的就是k的深度+k到i的链长+i的深度，与B数组定义相同 
        mx = max(mx,d[cv[i]]-sum); //注意要更新mx 
    }
    sum = mx = 0;
    double cn_1 = cw[tot]; //这里也很巧妙，把tot这个点的点权记录下来，也就是相当于把1和tot这条边断开 
    cw[tot] = 0; //要把tot这个点点权清零 
    drep(i,tot,1){ //预处理后缀，和前缀类似 
        sum += cw[i];
        C[i] = max(C[i+1],sum+d[cv[i]]);
        D[i] = max(D[i+1],mx+d[cv[i]]+sum);
        mx = max(mx,d[cv[i]]-sum);
    }
    double res;
    rep(i,1,tot){
        res = max(max(B[i],D[i+1]),A[i]+C[i+1]+cn_1); //上述所说的三段 
        res2 = min(res2,res); //使res2最小化 
    }
    res2 = min(res2,B[tot]); //别忘了加上特判 
    printf("%.1lf\n",max(res1,res2)/2);

总代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c)  for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int M = 2e5+10;
int n;
int head[M],vis[M],fa[M];
int inc[M],cv[M],cw[M],w[M];
double d[M],A[M],B[M],C[M],D[M];
int cnt,tot,ans;
double res1,res2=1e18;
struct edge{
    int to,nxt,w;
}e[M];
inline void add(int u,int v,int w){
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
inline bool find(int u){
    vis[u] = 1; //这个点记录为走过 
    for(re int i(head[u]) ; i ; i=e[i].nxt){
        int v = e[i].to;
        if(v == fa[u]) continue; //走到了父亲不行 
        fa[v] = u;
        w[v] = e[i].w; //将这条边的边权转化为儿子的点权，和树剖的转化类似 
        if(!vis[v]) { if(find(v)) return 1; } //如果这个点没有走过而且后面能找到环，就一直往回return 
        else{ //找到了环 
            int p = u; //枚举环上的点 
            while(1){
                inc[p] = 1; //inc[p]=1表示p在环上 
                cv[++tot] = p; //环上的点的编号，由于后面操作，我们需要重新编号 
                cw[tot] = w[p]; //环上这个编号点的点权 
                p = fa[p]; //由于记录了fa[p]是p的父亲，所以可以往回找 
                if(p == u) break; //环遍历完了 
            }
            return 1; //记录已经找到环 
        }
    }
    return 0; //没找到就继续往下找 
}
inline void dfs(int u,int fa){
    for(re int i(head[u]) ; i ; i=e[i].nxt){
        int v = e[i].to,w = e[i].w;
        if(inc[v] || v==fa) continue; //如果这个点在环上，或者搜到了父亲就不继续 
        dfs(v,u); //往下搜 
        res1 = max(res1,d[u]+d[v]+w); //求最大的直径 
        d[u] = max(d[u],d[v]+w); //顺道记录下来以u为根的最大深度 
    }
}
signed main(){
    n=read();
    rep(i,1,n){
        int u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
    find(1);
    rep(i,1,tot) dfs(cv[i],0);
    double sum=0,mx=0;
    rep(i,1,tot){ //预处理前缀 
        sum += cw[i-1]; //sum就是链长的加和 
        A[i] = max(A[i-1],sum+d[cv[i]]); //根据A数组的定义来推 
        B[i] = max(B[i-1],mx+d[cv[i]]+sum); //这里很巧妙
                                            //我们的mx记录的是i这个点之前的某一个点k的深度-k之前的链长 
                                            //也就是说，我们要求B数组，可以用一个抵消的思想
                                            //sum记录的是链长的加和，再加上mx，也就把k前面的链长消掉了
                                            //最后剩的就是k的深度+k到i的链长+i的深度，与B数组定义相同 
        mx = max(mx,d[cv[i]]-sum); //注意要更新mx 
    }
    sum = mx = 0;
    double cn_1 = cw[tot]; //这里也很巧妙，把tot这个点的点权记录下来，也就是相当于把1和tot这条边断开 
    cw[tot] = 0; //要把tot这个点点权清零 
    drep(i,tot,1){ //预处理后缀，和前缀类似 
        sum += cw[i];
        C[i] = max(C[i+1],sum+d[cv[i]]);
        D[i] = max(D[i+1],mx+d[cv[i]]+sum);
        mx = max(mx,d[cv[i]]-sum);
    }
    double res;
    rep(i,1,tot){
        res = max(max(B[i],D[i+1]),A[i]+C[i+1]+cn_1); //上述所说的三段 
        res2 = min(res2,res); //使res2最小化 
    }
    res2 = min(res2,B[tot]); //别忘了加上特判 
    printf("%.1lf\n",max(res1,res2)/2);
    return 0;
}