http://poj.org/problem?id=2728
题意：有n个点，有三个属性代表每个点在平面上的位置，和它的高度。点与点之间有一个花费：两点的高度差；还有一个长度：两点的距离。现在要让你在这n个点里面弄一个生成树，使得∑cost / ∑dis 最小，问最小的比率是多少。
思路：求得的比率R = ∑(cost[i] * x[i]) / ∑(dis[i] * x[i])，x[i]为1代表选这个点，转化一下，就是要minimize（R）。
设F（L） = ∑(cost[i] * x[i]) - ∑(dis[i] * L * x[i]) = ∑(cost[i] - dis[i] * L) * x[i] = ∑D[i] * x[i] （D[i] = cost[i] - L * dis[i]）。
我们要使得L越小越好，那么L越小，D[i]就会越大，因此我们要求得的是最小能达到的D[i]使得这个方程成立，这样的边界时候的L才是最小的。
那么我们可以先随便假设一个L，然后通过使用最小生成树（把上面的D[i]当做边权），判断当前的L还能够更优，当迭代到一定次数之后，就可以得出正确答案了（当然也可以二分搜索）。
具体写的很详细的：http://blog.csdn.net/hhaile/article/details/8883652
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 using namespace std; 5 #define N 10010 6 const double eps = 1e-7; 7 const double INF = 1000000000; 8 struct node { 9 double x, y, z; 10 } p[N]; 11 double low[N], cost[N][N], dis[N][N]; 12 int vis[N], pre[N], n; 13 14 double sqr(double x) { return x * x; } 15 16 double Prim(double k) { 17 double fz = 0, fm = 0, mi; int index; 18 for(int i = 1; i <= n; i++) low[i] = cost[1][i] - dis[1][i] * k, vis[i] = 0, pre[i] = 1; 19 vis[1] = 1; // 记得 20 for(int i = 1; i < n; i++) { 21 mi = INF, index = -1; 22 for(int j = 1; j <= n; j++) 23 if(!vis[j] && mi > low[j]) mi = low[index = j]; 24 if(index == -1) break; 25 vis[index] = 1; 26 fz += cost[index][pre[index]]; fm += dis[index][pre[index]]; 27 for(int j = 1; j <= n; j++) 28 if(!vis[j] && (cost[index][j] - dis[index][j] * k) < low[j]) 29 low[j] = cost[index][j] - dis[index][j] * k, pre[j] = index; 30 } 31 return fz / fm; 32 } 33 34 double solve() { 35 double ans = 0, tmp = 1; 36 while(1) { 37 tmp = Prim(ans); 38 if(fabs(tmp - ans) <= eps) break; 39 ans = tmp; 40 } 41 return tmp; 42 } 43 44 int main() { 45 while(~scanf("%d", &n), n) { 46 for(int i = 1; i <= n; i++) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z); 47 for(int i = 1; i <= n; i++) { 48 for(int j = i + 1; j <= n; j++) { 49 cost[i][j] = cost[j][i] = fabs(p[i].z - p[j].z); 50 dis[i][j] = dis[j][i] = sqrt(sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y)); 51 } 52 } 53 printf("%.3f\n", solve()); 54 } 55 return 0; 56 }
原文：http://www.cnblogs.com/fightfordream/p/6426127.html