题意：给n个点，可以将每个点的x，y的欧几里得距离(就是坐标系里两点距离公式)看作距离，z的差值即为费用差，求的是所有最小生成树中的min（边费用和/边距离和）。

思路：其实挑战P143有类似的列题，用的是二分枚举答案的方法，只不过不是树。这一题仅仅需要将题给图找出最小生成树，然后同样枚举即可。

虽然网上有许多高级的名词什么最优比率xxx之类的。。以及迭代的方法，不过我认为用二分也很好，易于想到也可以加深理解。

1 #include 
      
         2   3 #include 
       
          4   5 #include 
        
           6   7 #include 
         
            8   9 #include 
          
            10  11 #include 
           
             12 13 #include 
            
              14 15 #define MAXN 1005 16 17 #define INF 1000000000 18 19 #define eps 1e-7 20 21 using namespace std; 22 23 int n; 24 25 double Edge[MAXN][MAXN], lowcost[MAXN]; 26 27 int nearvex[MAXN]; 28 29 struct Point 30 31 { 32 33 int x, y, z; 34 35 }p[MAXN]; 36 37 double cal(int a, int b) 38 39 { 40 41 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)); 42 43 } 44 45 double prim(int src, double l) 46 47 { 48 49 double cost = 0, len = 0; 50 51 double sum = 0; 52 53 for(int i = 1; i <= n; i++) 54 55 { 56 57 nearvex[i] = src; 58 59 lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l; 60 61 } 62 63 nearvex[src] = -1; 64 65 for(int i = 1; i < n; i++) 66 67 { 68 69 double mi = INF; 70 71 int v = -1; 72 73 for(int j = 1; j <= n; j++) 74 75 if(nearvex[j] != -1 && lowcost[j] < mi) 76 77 { 78 79 v = j; 80 81 mi = lowcost[j]; 82 83 } 84 85 if(v != -1) 86 87 { 88 89 cost += abs(p[nearvex[v]].z - p[v].z); 90 91 len += Edge[nearvex[v]][v]; 92 93 nearvex[v] = -1; 94 95 sum += lowcost[v]; 96 97 for(int j = 1; j <= n; j++) 98 99 {100 101 double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l;102 103 if(nearvex[j] != -1 && tmp < lowcost[j])104 105 {106 107 lowcost[j] = tmp;108 109 nearvex[j] = v;110 111 }112 113 }114 115 }116 117 }118 119 return sum;120 121 }122 123 int main()124 125 {126 127 while(scanf("%d", &n) != EOF && n)128 129 {130 131 for(int i = 1; i <= n; i++)132 133 scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);134 135 for(int i = 1; i <= n; i++)136 137 for(int j = 1; j <= n; j++)138 139 Edge[i][j] = cal(i, j);140 141 double low = 0, high = 10.0; //其实二分20多次已经很足够了142 143 double l = 0.0, r = 100.0, mid;144 145 while(r - l > eps)146 147 {148 149 mid = (l + r) / 2;150 151 if(prim(1, mid) >= 0) l = mid;152 153 else r = mid;154 155 }156 157 printf("%.3f\n", r);158 159 }160 161 return 0;162 163 }