懒得学 Dinkelbach迭代法……二分卡过
完全图就不要用 (mathrm{O}(mlog m)) 的堆优化了……
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n, uu[1005], vv[1005], ww[1005], din;
double a[1005][1005], dis[1005], qaq[1005][1005], pap[1005][1005];
const double eps=1e-8;
bool vis[1005];
struct Node{
int idx;
double val;
}nd[1100005];
double qwq(int u, int v){
return sqrt((uu[u]-uu[v])*(uu[u]-uu[v])+(vv[u]-vv[v])*(vv[u]-vv[v]));
}
bool cmp(Node x, Node y){
return x.val>y.val;
}
bool chk(double lim){
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
a[i][j] = pap[i][j] - lim * qaq[i][j];
memset(vis, 0, sizeof(vis));
memset(dis, 127, sizeof(dis));
dis[1] = din = 0;
nd[++din] = (Node){1, 0.0};
double re=0.0;/*
while(din){
Node x=nd[1];
pop_heap(nd+1, nd+1+din, cmp);
din--;
if(vis[x.idx]) continue;
vis[x.idx] = true;
re += dis[x.idx];
for(int i=1; i<=n; i++)
if(!vis[i] && dis[i]>a[x.idx][i]){
dis[i] = a[x.idx][i];
nd[++din] = (Node){i, dis[i]};
push_heap(nd+1, nd+1+din, cmp);
}
}*/
for(int ii=1; ii<=n; ii++){
int maxi=0;
double orz=100000000.0;
for(int i=1; i<=n; i++)
if(!vis[i] && dis[i]<orz){
orz = dis[i];
maxi = i;
}
vis[maxi] = true;
re += orz;
for(int i=1; i<=n; i++){
if(!vis[i] && dis[i]>a[maxi][i])
dis[i] = a[maxi][i];
}
}
return re<=eps;
}
int main(){
while(scanf("%d", &n)!=EOF){
if(!n) break;
for(int i=1; i<=n; i++)
scanf("%d %d %d", &uu[i], &vv[i], &ww[i]);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++){
qaq[i][j] = qwq(i, j);
pap[i][j] = abs(ww[i]-ww[j]);
}
double l=0.0, r=10000000.0, mid, re;
while(fabs(r-l)>eps){
mid = (l + r) / 2.0;
if(chk(mid)) re = mid, r = mid;
else l = mid;
}
printf("%.3f
", re);
}
return 0;
}