题面

题目描述

小 $T$ 打算在城市 $C$ 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 $T$ 希望快餐店的地址选在离最远的顾客距离最近的地方。

快餐店的顾客分布在城市 C 的 $N$ 个建筑中，这 $N$ 个建筑通过恰好 $N$条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 $T$ 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。

现给定城市 $C$ 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。

输入格式

第一行包含一个整数 $N$，表示城市 $C$ 中的建筑和道路数目。

接下来 $N$ 行，每行 $3$ 个整数，$A_i,B_i,L_i$（$1\leq i\leq N$，$L_i>0$），表示一条道路连接了建筑 $A_i$​ 与 $B_i$​，其长度为 $L_i$。

输出格式

输出仅包含一个实数，四舍五入保留恰好一位小数，表示最佳快餐店选址距离最远用户的距离。

注意：你的结果必须恰好有一位小数，小数位数不正确不得分。

输入输出样例

输入 #1

4 
1 2 1 
1 4 2 
1 3 2 
2 4 1

输出 #1

2.0 

输入 #2

5
1 5 100
2 1 77
3 2 80
4 1 64
5 3 41

输出 #2

109.0

数据范围

• 对于 $10\%$ 的数据，$N≤80，L_i=1$；
• 对于 $30\%$ 的数据，$N≤600，L_i\leq 100$；
• 对于 $60\%$ 的数据，$N≤2000，L_i\leq 10^9$；
• 对于 $100\%$ 的数据，$1≤N≤10^5，1\leq L_i \leq 10^9$。

题解

简单转化后即为求基环树的最小直径与环外子树直径最大值中的最大值/2（这里不证明），考虑怎么求基环树的最小直径。

一个简单的基环树上求解树上问题的方法就是断环上一条边然后当成树来做，这个复杂度是$O(n^2)$的，考虑怎么优化，我们先$dfs$一遍把环上所有点以及所连向下一个环上点的边长给找出来(最后如图)，然后找出每个环上点向子树可以走的最大深度记为$MD$，然后就大力维护在$i$点前最大的起点子树深度+往前走的长度还有$i+1$ 点后最大的向后走的长度+终点子树深度 ，还有终点起点都在$i$点前的路径长度+两点子树深度的最大值和终点起点都在$i+1$点后的路径长度+两点子树深度的最大值。

对于每个不同的$i$求个最大情况的整体最小值就好了。

代码

#include<bits/stdc++.h>
#define Maxn 100005
#define gc getchar
#define isd isdigit
#define W while
#define LL long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
using namespace std;
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('\n');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='\n');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
struct edge{LL dis,next,to;}e[Maxn<<1];
LL Ans=0,ans=0,n,head[Maxn],cnt=0,ring[Maxn],Stack[Maxn],len[Maxn],f[Maxn],deep[Maxn],MD[Maxn],Min=2e18,tmp1[Maxn],tmp2[Maxn],suf[Maxn],pre[Maxn],suf1[Maxn],pre1[Maxn],suf2[Maxn],pre2[Maxn];
bool vis[Maxn],flag=0,is_ring[Maxn];
inline void add(LL u,LL v,LL w){e[++cnt].next=head[u];e[cnt].to=v;e[cnt].dis=w;head[u]=cnt;}
inline void dfs_ring(LL now,LL fa){if (flag) return;if (vis[now]){W (Stack[Stack[0]]!=now) ring[++ring[0]]=Stack[Stack[0]--];ring[++ring[0]]=Stack[Stack[0]--];flag=1;return;}Stack[++Stack[0]]=now;vis[now]=1;for (LL i=head[now];i;i=e[i].next){LL v=e[i].to;if (v==fa) continue;dfs_ring(v,now);}Stack[0]--;}
inline void dfs_dis_ring(LL now){if (now+1>ring[0]) return;for (LL i=head[ring[now]];i;i=e[i].next){LL v=e[i].to;if (v==ring[now+1]) len[now]=e[i].dis,dfs_dis_ring(now+1);}}
inline void dfs_son(LL now,LL fa) {MD[now]=deep[now];for (LL i=head[now];i;i=e[i].next) {LL v=e[i].to;if (v==fa||is_ring[v]) continue;deep[v]=deep[now]+e[i].dis;dfs_son(v,now);MD[now]=max(MD[now],MD[v]);ans=max(ans,f[now]+f[v]+e[i].dis);f[now]=max(f[now],f[v]+e[i].dis);}}
int main()
{
	fin>>n;for (LL u,v,w,i=1;i<=n;i++) fin>>u>>v>>w,add(u,v,w),add(v,u,w);
	dfs_ring(1,1);dfs_dis_ring(1);
	for (LL i=head[ring[ring[0]]];i;i=e[i].next){LL v=e[i].to;if (v==ring[1]) len[ring[0]]=e[i].dis;}
	for (LL i=1;i<=ring[0];i++) is_ring[ring[i]]=1;
	for (LL i=1;i<=ring[0];i++) ans=0,dfs_son(ring[i],ring[i]),Ans=max(Ans,ans);
//	cout<<Ans<<endl;
//	for (LL i=1;i<=ring[0];i++) cout<<"afsd "<<ring[i]<<" "<<len[i]<<endl;	
	for (LL i=1;i<=ring[0];i++) suf[i]=suf[i-1]+len[i];
	for (LL i=1;i<=ring[0]-1;i++) suf1[i]=max(suf1[i-1],suf[i-1]+MD[ring[i]]);
	for (LL i=1;i<=ring[0]-1;i++) tmp1[i]=max(tmp1[i-1],-suf[i-1]+MD[ring[i]]);
	for (LL i=1;i<=ring[0]-1;i++) suf2[i]=max(suf2[i-1],suf[i-1]+MD[ring[i]]+tmp1[i-1]);
	for (LL i=ring[0];i>=1;i--) pre[i]=pre[i+1]+len[i];
	for (LL i=ring[0];i>=1;i--) pre1[i]=max(pre1[i+1],pre[i]+MD[ring[i]]);
	for (LL i=ring[0];i>=1;i--) tmp2[i]=max(tmp2[i+1],-pre[i]+MD[ring[i]]);
	for (LL i=ring[0];i>=1;i--) pre2[i]=max(pre2[i+1],pre[i]+MD[ring[i]]+tmp2[i+1]);
	for (LL i=1;i<=ring[0]-1;i++) Min=min(Min,max(max(suf2[i],pre2[i+1]),suf1[i]+pre1[i+1]));
	printf("%.1lf\n",(double)max(Ans,Min)/2);
	return 0;
}
/*
5
1 5 100
2 1 77
3 2 80
4 1 64
5 3 41
*/