题意：给你一个只有一个环的图，让你选一个点（可以在边上），使得到最远点的最短路最小。
思路：
如果是一颗树的话，就是求树的直径/2。
如果是基环树的话，这道题显然不是基环树的直径，因为是到最远点的最短路的缘故。
那我们考虑最终解到其他所有点的最短路中，一定没有环，所以一定是一棵树。
所以我们枚举基环树所有可能出现的树，即枚举在环上去一条边，求树的直径。
显然最后，我们需要得到的很多解中取最小值，明显其他的不符合最短路。
当然如果基环树的直径在树中的话，答案肯定就是基环树的直径。
暴力的复杂度是o(n*n)的，但是这道题与求基环树的直径的唯一区别就是环上取的是最小值。
所有dp滑一下就好了。
考虑开始环断开一条边变成一条链，链上一个点的解一定是前缀的最大值，后缀的最大值，前后缀交的最大值取最大。
#include <bits/stdc++.h> using namespace std; #define N 100005 #define ll long long struct edge{ int to,n;ll w; };edge d[N*2]; int h[N],vis[N],q[N], tot=1,r=0; void add(int x,int y,ll w){ d[tot]={y,h[x],w};h[x]=tot++; d[tot]={x,h[y],w};h[y]=tot++; } ll ans2,ans1,sum,maa,ma1[N],ma2[N],dis[N]; int getloof(int u,int fa){ vis[u]=1; for(int i=h[u];i;i=d[i].n){ int to=d[i].to; if(to==fa)continue; if(vis[to]){ q[++r]=u;dis[r]=d[i].w; return to; } int key=getloof(to,u); if(key){ q[++r]=u;dis[r]=d[i].w; return key!=u?key:0; } } return 0; } void dfs(int u){ vis[u]=1; for(int i=h[u];i;i=d[i].n){ int to=d[i].to; if(vis[to])continue; dfs(to); if(ma1[to]+d[i].w>=ma1[u]){ ma2[u]=ma1[u]; ma1[u]=ma1[to]+d[i].w; } else ma2[u]=max(ma2[u],ma1[to]+d[i].w); } ans1=max(ans1,ma1[u]+ma2[u]); } ll dp1[N],dp2[N],dp3[N],dp4[N]; void solve(){ memset(vis,0,sizeof(vis)); for(int i=1;i<=r;i++)vis[q[i]]=1; for(int i=1;i<=r;i++)dfs(q[i]); sum=0;dp1[1]=dp3[1]=maa=ma1[q[1] ]; for(int i=2;i<=r;i++) dp1[i]=max(dp1[i-1],(sum+=dis[i])+ma1[q[i]]), dp3[i]=max(dp3[i-1],ma1[q[i]]+(maa+=dis[i])), maa=max(ma1[q[i]],maa); sum=0;dp2[r]=dp4[r]=maa=ma1[q[r]]; for(int i=r-1;i;i--) dp2[i]=max(dp2[i+1],(sum+=dis[i+1])+ma1[q[i]]), dp4[i]=max(dp4[i+1],ma1[q[i]]+(maa+=dis[i+1])), maa=max(ma1[q[i]],maa); ans2=dp3[r]; for(int i=1;i<r;i++) ans2=min(ans2,max(dp1[i]+dp2[i+1]+dis[1],max(dp3[i],dp4[i+1]))); printf("%.1f\n",max(ans1,ans2)/2.); } int main() { int n,x,y,w; cin>>n; for(int i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&w); add(x,y,w); } getloof(1,0); solve(); return 0; }
