题目链接：https://vjudge.net/problem/POJ-2728

题目意思：给你n个村庄的坐标和每个村庄的海拔。建设管道需要花费(为两村庄高度差)。现在求 总花费/总距离(各条线路的距离)的最小值。

思路：https://www.jianshu.com/p/d40a740a527e

0/1规划，最优入门题。用链式前向星、Dis数组放外面会T成SB

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<iomanip>
 5 #include<algorithm>
 6 #include<string.h>
 7 #define eqs 1e-6;
 8 using namespace std;
 9 const int MAXN = 1010;
10 const int INF = 999999;
11 double Graph[MAXN][MAXN];
12 struct P{
13     double x,y,z;
14 }Cy[MAXN];
15 int N;
16 double distance(double x1,double y1,double x2,double y2){
17     double ret=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
18     return sqrt(ret);
19 }
20 void UpdateMap(double l){
21     for(int i = 1;i <= N;i ++){
22         for(int j = 1;j <= N;j ++){
23             Graph[i][j] = fabs(Cy[i].z - Cy[j].z) - l * distance(Cy[i].x,Cy[i].y,Cy[j].x,Cy[j].y);
24         }
25     }
26 }
27 double dis[MAXN];
28 double prim(){
29     double minn;
30     double sum = 0;
31     bool vis[MAXN];
32     int now;
33     memset(vis,0,sizeof(vis));
34     for(int i = 1;i <= N;i ++){
35         dis[i] = Graph[1][i];
36     }
37     vis[1] = 1;
38     for(int i = 1;i <= N;i ++){
39         minn = INF;
40         for(int j = 1;j <= N;j++){
41             if(!vis[j]){
42                 if(dis[j] < minn){
43                     now = j;
44                     minn = dis[j];
45                 }
46             }
47         }
48         if(minn == INF) break;
49         sum += minn;
50         vis[now] = 1;//cout<<"i = "<<i<<endl;
51         for(int j = 1;j <= N;j ++){
52             if(!vis[j] && dis[j] >= Graph[now][j])
53                 dis[j] = Graph[now][j];
54         }
55     }
56     return sum;
57 }
58 int main(){
59     while(cin>>N,N){
60         for(int i = 1;i <= N;i ++){
61             cin>>Cy[i].x>>Cy[i].y>>Cy[i].z;
62         }
63         double high = 100.0;
64         double low = 0.0 , pre = 0.0;
65         double mid,ans;
66         while(low <= high){
67             mid = (high + low)/2;
68             UpdateMap(mid);
69             ans = prim();
70             if(fabs(pre - ans) <= 0.0005) break;
71             if(ans > 0.0005) low = mid;
72             else high = mid;
73         }
74 //        cout<<fixed<<setprecision(3)<<mid<<endl;
75         printf("%.3lf\n",mid);
76     }
77     return 0;
78 }