#include <iostream> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> #define MAXN 1005 #define INF 1000000000 #define eps 1e-7 using namespace std; int n; double Edge[MAXN][MAXN], lowcost[MAXN]; int nearvex[MAXN]; struct Point { int x, y, z; }p[MAXN]; double cal(int a, int b) { return sqrt(1.0 * (p[a].x - p[b].x) * (p[a].x - p[b].x) + 1.0 * (p[a].y - p[b].y) * (p[a].y - p[b].y)); } double prim(int src, double l) { double cost = 0, len = 0; double sum = 0; for(int i = 1; i <= n; i++) { nearvex[i] = src; lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l; } nearvex[src] = -1; for(int i = 1; i < n; i++) { double mi = INF; int v = -1; for(int j = 1; j <= n; j++) if(nearvex[j] != -1 && lowcost[j] < mi) { v = j; mi = lowcost[j]; } if(v != -1) { cost += abs(p[nearvex[v]].z - p[v].z); len += Edge[nearvex[v]][v]; nearvex[v] = -1; sum += lowcost[v]; for(int j = 1; j <= n; j++) { double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l; if(nearvex[j] != -1 && tmp < lowcost[j]) { lowcost[j] = tmp; nearvex[j] = v; } } } } return sum; } int main() { while(scanf("%d", &n) != EOF && n) { for(int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) Edge[i][j] = cal(i, j); double low = 0, high = 10.0; double l = 0.0, r = 100.0, mid; while(r - l > eps) { mid = (l + r) / 2; if(prim(1, mid) >= 0) l = mid; else r = mid; } printf("%.3f\n", r); } return 0; }
此外，采用Dinkelbach进行迭代，复杂度更低一些，苣蒻在这里就不详述了，代码如下：
#include <iostream> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> #define MAXN 1005 #define INF 1000000000 #define eps 1e-7 using namespace std; int n; double Edge[MAXN][MAXN], lowcost[MAXN]; int nearvex[MAXN]; struct Point { int x, y, z; }p[MAXN]; double cal(int a, int b) { return sqrt(1.0 * (p[a].x - p[b].x) * (p[a].x - p[b].x) + 1.0 * (p[a].y - p[b].y) * (p[a].y - p[b].y)); } double prim(int src, double l) { double cost = 0, len = 0; for(int i = 1; i <= n; i++) { nearvex[i] = src; lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l; } nearvex[src] = -1; for(int i = 1; i < n; i++) { double mi = INF; int v = -1; for(int j = 1; j <= n; j++) if(nearvex[j] != -1 && lowcost[j] < mi) { v = j; mi = lowcost[j]; } if(v != -1) { cost += abs(p[nearvex[v]].z - p[v].z); len += Edge[nearvex[v]][v]; nearvex[v] = -1; for(int j = 1; j <= n; j++) { double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l; if(nearvex[j] != -1 && tmp < lowcost[j]) { lowcost[j] = tmp; nearvex[j] = v; } } } } return cost / len; } int main() { while(scanf("%d", &n) != EOF && n) { for(int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) Edge[i][j] = cal(i, j); double a = 0, b; while(1) { b = prim(1, a); if(fabs(a - b) < eps) break; a = b; } printf("%.3f\n", b); } return 0; }
原文：http://www.cnblogs.com/Enceladus/p/4979082.html