Luogu

分析

双倍经验

答案就是删掉一条边后树的直径的一半的最小值。

删掉一条边后树的直径的最小值可以参照这个题求。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
#define mp make_pair
#define IT multiset<pair<int,int>,greater<pair<int,int> > >::iterator
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n;
struct Edge { int v,w,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int eid[N],in[N],fa[N];
int dfn[N],tim=0,top=0;
pair<int,int> cir[N];
int f[N],mx;
int sum[N];
set<pair<int,int>,greater<pair<int,int> > > s1,s2;

inline void find_circle(int u) {
    dfn[u]=++tim;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa[u]) continue;
        if (dfn[v]) {
            if (dfn[v]<dfn[u]) continue;
            for (re int i=v;i!=u;i=fa[i])
                cir[++top]=mp(i,e[eid[i]].w),in[i]=1;
            cir[++top]=mp(u,e[i].w),in[u]=1;
            return;
        }
        fa[v]=u,eid[v]=i; find_circle(v);
        if (top) return;
    }
}

inline void dfs(int u,int fa) {
    f[u]=0; int mx1=0,mx2=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;; if (v==fa||in[v]) continue;
        dfs(v,u); f[u]=max(f[u],f[v]+w);
        if (f[v]+w>mx1) mx2=mx1,mx1=f[v]+w;
        else if (f[v]+w>mx2) mx2=f[v]+w;
    }
    mx=max(mx,mx1+mx2);
}

signed main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    find_circle(1);
    for (re int i=1;i<=top;++i)
        cir[i+top]=cir[i],dfs(cir[i].first,0);
    for (re int i=2;i<=top*2;++i) sum[i]=sum[i-1]+cir[i-1].second;
    for (re int i=1;i<=top;++i) {
        s1.insert(mp(f[cir[i].first]+sum[i],i));
        s2.insert(mp(f[cir[i].first]-sum[i],i));
    }
    int ans=1e18;
    for (re int i=1;i<=top;++i) {
        int now;
        if (s1.begin()->second==s2.begin()->second) {
            IT it=s1.begin(); ++it;
            now=it->first+s2.begin()->first;
            it=s2.begin(); ++it;
            now=max(now,it->first+s1.begin()->first);
        }
        else now=s1.begin()->first+s2.begin()->first;
        ans=min(ans,now);
        s1.erase(mp(f[cir[i].first]+sum[i],i));
        s2.erase(mp(f[cir[i].first]-sum[i],i));
        s1.insert(mp(f[cir[i+top].first]+sum[i+top],i+top));
        s2.insert(mp(f[cir[i+top].first]-sum[i+top],i+top));
    }
    printf("%.1lf\n",max(ans,mx)/2.0);
    return 0;
}
最后修改:2019 年 09 月 28 日 10 : 20 PM