题意：
给定n个村子的坐标（x,y）和高度z， 求出修n-1条路连通所有村子， 并且让 修路花费/修路长度 最少的值
两个村子修一条路， 修路花费 = abs(高度差), 修路长度 = 欧氏距离
分析：
01分数划分的题目， 构造出 d[i] = 修路花费 - L * 修路长度， 这个L值我们可以二分（这道题看数据范围的话二分上限其实挺大的， 但其实上限取到100就可以过）， 也可以用Dinkelbach迭代出来。
二分（1422ms）
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#define rep(i,a,b) for(int i = a; i < b;i++)
#define _rep(i,a,b) for(int i = a; i <= b;i++)
using namespace std;
const int maxn = + ;
const double inf = 1e9 + ;
const double eps = 1e-;
int n; double G[maxn][maxn];
double x[maxn], y[maxn], z[maxn]; inline double p2p_dis(double x1, double y1, double x2, double y2){
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double prim(double L){
double tree_dis = ;
double dis[maxn];
int vis[maxn];
fill(dis, dis + maxn, inf);
memset(vis, ,sizeof(vis)); dis[] = ;
vis[] = ; for(int i = ; i < n; i++) dis[i] = abs(z[] - z[i]) - L * G[][i]; for(int times = ; times < n - ; times++){
int picked = -;
double min_dis = inf;
for(int i = ; i < n; i++){
if(!vis[i] && dis[i] < min_dis){
min_dis = dis[i];
picked = i;
}
}
tree_dis += min_dis;
vis[picked] = ;
for(int i = ; i < n; i++)
if(!vis[i])
dis[i] = min(dis[i] , abs(z[picked] - z[i]) - L * G[picked][i]) ;
}
return tree_dis;
} int main(){
// freopen("1.txt","r", stdin);
while(cin >> n && n){
rep(i,,n) cin >> x[i] >> y[i] >> z[i];
rep(i,,n) rep(j,i+,n) G[i][j] = G[j][i] = p2p_dis(x[i],y[i],x[j],y[j]);
double l = , r = ;
while(abs(r - l) > eps){
double mid = (l + r) / ;
// printf("%.3f\n", mid);
if(prim(mid) >= ){
l = mid;
}else{
r = mid;
}
}
printf("%.3f\n", l);
}
return ;
}
Dinkelbach（204ms）
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#define rep(i,a,b) for(int i = a; i < b;i++)
#define _rep(i,a,b) for(int i = a; i <= b;i++)
using namespace std;
const int maxn = + ;
const double inf = 1e9 + ;
const double eps = 1e-;
int n; double G[maxn][maxn];
double x[maxn], y[maxn], z[maxn]; inline double p2p_dis(double x1, double y1, double x2, double y2){
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double prim(double L){
double ele = , deno = ; //分子分母
double dis[maxn];
int near[maxn]; //开一个数组记录每次选中是哪一条边 int vis[maxn];
fill(dis, dis + maxn, inf);
memset(vis, ,sizeof(vis));
memset(near, -, sizeof(near));
dis[] = ;
vis[] = ; for(int i = ; i < n; i++) dis[i] = abs(z[] - z[i]) - L * G[][i], near[i] = ; //每个点都是由0点更新的， 所以near都是0 for(int times = ; times < n - ; times++){
int picked = -;
double min_dis = inf;
for(int i = ; i < n; i++){
if(!vis[i] && dis[i] < min_dis){
min_dis = dis[i];
picked = i;
}
}
ele += abs(z[near[picked]] - z[picked]);//分子是选的路程
deno += G[near[picked]][picked]; //分母是真实的花费
vis[picked] = ;
for(int i = ; i < n; i++)
if(!vis[i] && dis[i] > abs(z[picked] - z[i]) - L * G[picked][i]){
dis[i] = abs(z[picked] - z[i]) - L * G[picked][i];
near[i] = picked;//如果通过picked点更新dis，那么该位置near就是picked
} } return ele/deno; //注意返回的跟二分不一样， 应该返回当前L下真正题目的所求
} int main(){
// freopen("1.txt","r", stdin);
while(cin >> n && n){
rep(i,,n) cin >> x[i] >> y[i] >> z[i];
rep(i,,n) rep(j,i+,n) G[i][j] = G[j][i] = p2p_dis(x[i],y[i],x[j],y[j]);
double L, ans = ;
while(){
L = ans;
ans = prim(L); //这是一个真实值， 不是含L的变式
if(abs(ans - L)< eps) break;
}
printf("%.3f\n", ans);
}
return ;
}