题意：
给定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 = 1000 + 7; const double inf = 1e9 + 7; const double eps = 1e-5; 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 = 0; double dis[maxn]; int vis[maxn]; fill(dis, dis + maxn, inf); memset(vis, 0 ,sizeof(vis)); dis[0] = 0; vis[0] = 1; for(int i = 1; i < n; i++) dis[i] = abs(z[0] - z[i]) - L * G[0][i]; for(int times = 0; times < n - 1; times++){ int picked = -1; double min_dis = inf; for(int i = 0; i < n; i++){ if(!vis[i] && dis[i] < min_dis){ min_dis = dis[i]; picked = i; } } tree_dis += min_dis; vis[picked] = 1; for(int i = 0; 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,0,n) cin >> x[i] >> y[i] >> z[i]; rep(i,0,n) rep(j,i+1,n) G[i][j] = G[j][i] = p2p_dis(x[i],y[i],x[j],y[j]); double l = 0, r = 14143000; while(abs(r - l) > eps){ double mid = (l + r) / 2; // printf("%.3f ", mid); if(prim(mid) >= 0){ l = mid; }else{ r = mid; } } printf("%.3f ", l); } return 0; }
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 = 1000 + 7; const double inf = 1e9 + 7; const double eps = 1e-5; 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 = 0, deno = 0; //分子分母 double dis[maxn]; int near[maxn]; //开一个数组记录每次选中是哪一条边 int vis[maxn]; fill(dis, dis + maxn, inf); memset(vis, 0 ,sizeof(vis)); memset(near, -1, sizeof(near)); dis[0] = 0; vis[0] = 1; for(int i = 1; i < n; i++) dis[i] = abs(z[0] - z[i]) - L * G[0][i], near[i] = 0; //每个点都是由0点更新的， 所以near都是0 for(int times = 0; times < n - 1; times++){ int picked = -1; double min_dis = inf; for(int i = 0; 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] = 1; for(int i = 0; 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,0,n) cin >> x[i] >> y[i] >> z[i]; rep(i,0,n) rep(j,i+1,n) G[i][j] = G[j][i] = p2p_dis(x[i],y[i],x[j],y[j]); double L, ans = 0; while(1){ L = ans; ans = prim(L); //这是一个真实值， 不是含L的变式 if(abs(ans - L)< eps) break; } printf("%.3f ", ans); } return 0; }