NOI2013 快餐店

题目:

   小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。
   快餐店的顾客分布在城市 C 的 个建筑中,这 个建筑通过恰好 条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中,也可以开设在任意一条道路的某个位置上(该位置与道路两端的建筑的距离不一定是整数)。
   现给定城市 C 的地图(道路分布及其长度),请找出最佳的快餐店选址,输出其与最远的顾客之间的距离。

思路:

   个点条边,也就是说题目所给的是一棵基环树。那么所有不经过环的路径是不会受快餐店的影响发生变化的,所以可以把这些路径直接计入答案了。当快餐店的位置确定时,环上的“左边”的点都会走“左边”,“右边”的点都会走“右边”(如下图,当绿色为快餐店时,红色为“左边”,黄色为“右边”,蓝色部分就没人走了):
           
   所以环上一定有一条边是不出现在最优决策里的,所以的暴力可以枚举这条边,在剩下的树里求直径。
   每次图中只变化了一条边,所以可以考虑优化在树中求直径的过程。在一个环中删掉一条边后(图中的蓝色边),最长的路径只有三种情况(黄色边):
  
   对于每条边,可以递推求出在“左侧选择一条路径的最大值”,“右侧选择一条路径的最大值”,“左侧选择一条到环的最左侧的路径的最大值”,“右侧选择一条到环的最右侧的路径的最大值”。就能表达出这三种情况了,求两点间中的最大距离,可以先预处理出表示从到子树内的最长链,到最左侧的距离,那么分开维护一个前\后缀最大值就行了(具体见代码)。

代码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
#define erep(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
#define max3(a,b,c) std::max(std::max(a,b),c)
#define File(_) freopen(#_".in","r",stdin),freopen(#_".out","w",stdout)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){memset(HEAD,0,sizeof HEAD);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
};
typedef long long ll;
const int MN=1e5+5;
struct Edge{int to,w;};
Link<MN,MN<<1,Edge> G;
int ufs[MN],nxt[MN],vec[MN],tot;
int find(int x){return ufs[x]==x?x:ufs[x]=find(ufs[x]);}
bool vis[MN],inc[MN];
bool dfs_cir(int o,int f){
    if(vis[o])return true;
    vis[o]=true;
    erep(k,G,o){
        int v=G[k].to,d=G[k].w;
        if(v==f)continue;
        if(dfs_cir(v,o)){
            nxt[v]=o;
            return true;
        }
    }
    return false;
}
ll mx[MN],smx[MN],ans;
void dfs_tre(int o,int f){
    mx[o]=smx[o]=0;
    erep(k,G,o){
        int v=G[k].to;
        if(v==f||inc[v])continue;
        dfs_tre(v,o);
        tomax(smx[o],mx[v]+G[k].w);
        if(smx[o]>mx[o])
            std::swap(mx[o],smx[o]);
    }
    tomax(ans,mx[o]+smx[o]);
}
ll val[MN],dis[MN],s[MN],mxL[MN],mxR[MN],valR[MN],valL[MN];
ll calc(){
    rep(i,1,tot)
        val[i]=mx[vec[i]];
    rep(i,2,tot+1)
        s[i]=s[i-1]+dis[i-1];
    ll mx=0;
    rep(i,1,tot){
        mxL[i]=std::max(s[i]+val[i]+mx,mxL[i-1]);
        valL[i]=std::max(s[i]+val[i],valL[i-1]);
        tomax(mx,-s[i]+val[i]);
    }
    mx=0;
    drep(i,tot,1){
        mxR[i]=std::max(s[tot+1]-s[i]+val[i]+mx,mxR[i+1]);
        valR[i]=std::max(s[tot+1]-s[i]+val[i],valR[i+1]);
        tomax(mx,s[i]-s[tot+1]+val[i]);
    }
    ll ans=4e18;
    rep(i,0,tot)
        tomin(ans,max3(mxL[i],mxR[i+1],valL[i]+valR[i+1]));
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    rep(i,1,n)ufs[i]=i;
    int cn;
    rep(i,1,n){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        G.add(a,(Edge){b,c});
        G.add(b,(Edge){a,c});
        if(find(a)==find(b))
            cn=a;
        else ufs[find(a)]=find(b);
    }
    dfs_cir(cn,0);
    for(int t=nxt[cn];;t=nxt[t]){
        erep(k,G,t)
            if(G[k].to==nxt[t])
                dis[++tot]=G[k].w;
        vec[tot]=t;
        inc[t]=true;
        if(t==cn)break;
    }
    rep(i,1,tot)dfs_tre(vec[i],0);
    tomax(ans,calc());
    printf("%lld.%d\n",ans>>1,(ans&1)?5:0);
    return 0;
}