392 基环树 P1399 [NOI2013] 快餐店

视频链接：

// Luogu P1399 [NOI2013] 快餐店
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100000+10;
int n;
struct edge{int v,w,ne;}e[N<<1];
int h[N],idx;
int vis[N],fa[N],w[N];
int inc[N],cv[N],cw[N],cn;
double d[N],A[N],B[N],C[N],D[N];
double ans1,ans2=1e18;

void add(int a,int b,int c){
    e[++idx]={b,c,h[a]};h[a]=idx;
}
bool find(int u){
    vis[u]=true;
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(v!=fa[u]){
            fa[v]=u; w[v]=e[i].w;      
            if(!vis[v]){//v尚未访问
                if(find(v))return 1;
            }
            else{//v已访问
                int p=u;
                while(1){
                    inc[p]=1;cv[++cn]=p;
                    cw[cn]=w[p];p=fa[p];
                    if(p==u)break;
                }    
              return 1;
            }
        }
    }
    return 0;
}
void dfs(int u,int fa){
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v, w=e[i].w;
        if(!inc[v]&&v!=fa){
            dfs(v,u);
            ans1=max(ans1,d[u]+d[v]+w);
            d[u]=max(d[u],d[v]+w);
        }
    }
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);add(y,x,z);
  }
    find(1);//深搜找环
    for(int i=1;i<=cn;++i)
      dfs(cv[i],0);//深搜求直径ans1
    double sum=0,mx=0;
    for(int i=1;i<=cn;++i){//求前缀
        sum+=cw[i-1];
        A[i]=max(A[i-1],sum+d[cv[i]]);
        B[i]=max(B[i-1],mx+d[cv[i]]+sum);
        mx=max(mx,d[cv[i]]-sum);
    }
    sum=mx=0;
    double cn_1=cw[cn];cw[cn]=0;
    for(int i=cn;i>=1;--i){//求后缀
        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;
    for(int i=1;i<cn;++i){//拼凑答案
        res=max(max(B[i],D[i+1]),
                A[i]+C[i+1]+cn_1);
        ans2=min(ans2,res);
    }
    printf("%.1lf",max(ans1,ans2)/2);
  return 0;
}