CF266D BerDonalds

思路

最小直径生成树板子题。
假设答案是 $ans$。
首先发现 $n$ 是非常小的，所以我们可以先用 Floyd 跑出所有点两两之间的距离。
然后最优点可能在点上，也可能在边上。
我们先考虑在点上的情况。
假设 $i,j$ 之间的距离为 $dis_{i,j}$，那么将中心设在 $u$ 时，最大距离即为最大的 $v\in [1,n],dis_{u,v}$。
枚举所有点，找到最小的一个最大距离，更新 $ans$。
然后考虑在边上的情况，容易发现一定是在最长的一条路径的中点会最优。
存下所有边并枚举，假设端点是 $u,v$，长度是 $w$。
那么点 $a$ 到达取到点的距离即为 $dis_{u,a}$ 加上 $u$ 到取到点的距离和 $dis_{v,a}$ 加上 $v$ 到取到点的距离。
假设 $u$ 到取到点的距离为 $x$，则 $a$ 到取到点的距离为 $\min{dis_{u,a}+x,dis_{v,a}+(w-x)}$。
那么这个东西的左边值与 $x$ 同增，右边值与 $x$ 同减。
当 $x$ 取到特定值的时候可以让左右两个值相等。
画出这个式子的图像后可以得到一条单峰的折线，且斜率的绝对值等于 $1$。
那么对于 $a\in[1,n]$，就是对所有折线取 $\max$，最后大概长这样（oi-wiki 的图）：

那么最小值一定处于两条折线的交点处（下坡走完了，必须走上坡）。
而观察图像，我们发现交点一定是由两条起始点（$dis_{u,a}$）相邻的折线组成。
那我们按照 $dis_{u,a}$ 对于所有点排序再找交点并更新答案即可。

提示

对于小数处理：所有路径长都是整数，那么小数位只会是 .0 或 .5。
所以在开始时先将所有长度 $\times2$，然后最后先输出 $ans\div 2$（即真正的整数部分），若 $ans\equiv 1\pmod 2$，再输出 .5 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=205;
const int inf=1e10;
int n,m,ans;
int dis[N][N];
struct node{
	int u,v,w;
};
vector<node>edges;
void floyd(){
    rep(k,1,n)rep(i,1,n)rep(j,1,n)
    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
signed main(){
	read(n,m);
	rep(i,1,n)rep(j,1,n)dis[i][j]=inf;
    rep(i,1,n)dis[i][i]=0;
    rep(i,1,m){
    	int u,v,w;
    	read(u,v,w);w*=2;
    	if(u==v)continue;
    	if(dis[u][v]<w)continue;
        dis[u][v]=dis[v][u]=w;
        edges.emplace_back(node{u,v,w});
    }
    floyd();
    ans=inf;
    rep(i,1,n){
        int mx=0;
        rep(j,1,n)mx=max(mx,dis[i][j]);
        ans=min(ans,mx);
    }
    fep(j,0,edges.size()){
    	int u=edges[j].u;
    	int v=edges[j].v;
    	int w=edges[j].w;
        vector<pii>order;order.clear();
        rep(p,1,n)order.emplace_back(dis[u][p],p);
        sort(order.begin(),order.end());
        reverse(order.begin(),order.end());
        int mx=-inf;
        fep(i,0,n){
            int p=order[i].second;
            if(mx!=-inf){
                int x=(mx-order[i].first+w)/2;
                if(x>0&&x<w)ans=min(ans,(order[i].first+mx+w)/2);
            }
            mx=max(mx,dis[v][p]);
        }
    }
    print(ans/2);
    if(ans%2==1)puts(".5");
}