InputThe first line contains an integer t meaning that there are t test cases(t <= 10).
For each test case:
The first line is an integer n meaning that there are n cities(2 < n <= 1000).
Then n lines follow. Each line contains three integers X, Y and P ( 0 <= X, Y <= 1000, 0 < P < 100000). (X, Y) is the coordinate of a city and P is the population of that city.
It is guaranteed that each city has a distinct location.OutputFor each test case, print a line indicating the above mentioned maximum ratio A/B. The result should be rounded to 2 digits after decimal point.Sample Input
2 4 1 1 20 1 2 30 200 2 80 200 1 100 3 1 1 20 1 2 30 2 2 40
Sample Output
65.00 70.00
题意：有n个村庄，现在要在这些村庄之间修建道路，保证所有村庄都能相互连通，修建道路的花费等于道路的长度，现在你有一个神奇的宝贝。它能够帮你修建一条无限长的到路并且没有任何花费。你肯定非把这个宝贝花在最长道路上，
但是现在要求这个宝贝要用在A/B的值最大的道路上，其中A表示道路两头村庄的人数和，B表示你除了这个道路以外你修建的其他道路的花费和。输入为每个村庄的坐标以及这个村庄的人数，有多组输入样例，对于每个样例你都要输出
最大的A/B的值，并且结果保留两位小数。
思路：要保证A/B最大，首先要保证B最小，因此可以得出第一步是先求出所有村庄连通的道路的花费的最小值，也就是最小生成树，然后看你的那个宝贝用在哪条道路，则有非用到次小生成树算法，最后求出结果即可
最小生成树算法个人总结：https://www.cnblogs.com/mzchuan/p/11720280.html
次小生成树算法个人总结：https://www.cnblogs.com/mzchuan/p/11828010.html
代码：
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 998244353 16 #define eps 1e-6 17 #define ll long long 18 #define INF 0x3f3f3f3f 19 using namespace std; 20 21 //ma存放两点之间的初始距离 22 double ma[1000][1000]; 23 //low存放到起点的最小距离， 24 double low[1000]; 25 //per存放与当前点连接距离最短的另一个点 26 int per[1000]; 27 //bj用于判断该点时候在生成树中，con用于标记在生成树中的边 28 bool bj[1000],con[1000][1000]; 29 //maxn存放两点之间的最大值 30 double maxn[1000][1000]; 31 int n; 32 //点的坐标以及人数 33 struct node 34 { 35 double x,y; 36 double s; 37 }; 38 node no[1000]; 39 //计算两点之间的距离 40 double dis(node a,node b) 41 { 42 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 43 } 44 //最小生成树算法,u表示树的起点 45 double secondprim(int u) 46 { 47 for(int i=0;i<n;i++) 48 { //初始low的距离与per指向的点 49 low[i]=ma[u][i]; 50 per[i]=u; 51 } 52 //初始化标记 53 memset(bj,0,sizeof(bj)); 54 memset(con,0,sizeof(con)); 55 //起点是树上的第一个点，标记 56 bj[u]=1; 57 //ans保存树的所有权值和 58 double ans=0; 59 //遍历其他n-个点 60 for(int i=0;i<n-1;i++) 61 { 62 //通过遍历找到距离当前起点的最短的边 63 double mi=INF; 64 int v=-1; 65 for(int j=0;j<n;j++) 66 { 67 if(!bj[j]&&low[j]<mi) 68 { 69 v=j; 70 mi=low[j]; 71 } 72 } 73 //有最短边后 74 if(v!=-1) 75 { 76 //将这个边的两个点标记 77 con[v][per[v]]=con[per[v]][v]=1; 78 //累加权值 79 ans+=mi; 80 //标记这个点 81 bj[v]=1; 82 //记录这个边的值， 83 maxn[per[v]][v]=maxn[v][per[v]]=mi; 84 //再遍历一遍，以更新数据 85 for(int j=0;j<n;j++) 86 { 87 //j表示的点再树上，且j不是终点 88 if(bj[j]&&j!=v) 89 { //更新v与其他在树上的点之间的最大权值 90 maxn[j][v]=maxn[v][j]=max(maxn[j][per[v]],maxn[per[v]][v]); 91 } 92 //j表示的点不在树上，且满足更新需要 93 if(!bj[j]&&low[j]>ma[v][j]) 94 { 95 //更新low的距离和per指向的点 96 low[j]=ma[v][j]; 97 per[j]=v; 98 } 99 } 100 } 101 } 102 //非严格次小生成树 103 double ansed=0; 104 //遍历所有点与其他点 105 //求最小的A/B,A表示这个边两头的人数和， 106 for(int i=0;i<n-1;i++) 107 { 108 for(int j=i+1;j<n;j++) 109 { 110 //如果这两个点不在树上 111 if(!con[i][j]) 112 { 113 //B表示s 删除 加上一个权值后形成的闭环的最大权值 114 ansed=max(ansed,(no[i].s+no[j].s)/(ans-maxn[i][j])); 115 }//如果者两个点在树上 116 else 117 { 118 ansed=max(ansed,(no[i].s+no[j].s)/(ans-ma[i][j])); 119 } 120 } 121 } 122 return ansed; 123 } 124 int main() 125 { 126 int t; 127 scanf("%d",&t); 128 while(t--) 129 { 130 scanf("%d",&n); 131 for(int i=0;i<n;i++) 132 { 133 scanf("%lf %lf %lf",&no[i].x,&no[i].y,&no[i].s); 134 } 135 //将点的坐标转换成点的距离信息 136 for(int i=0;i<n;i++) 137 { 138 for(int j=i;j<n;j++) 139 { 140 ma[j][i]=ma[i][j]=dis(no[i],no[j]); 141 } 142 } 143 printf("%0.2lf\n",secondprim(0)); 144 } 145 }
Qin Shi Huang's National Road System HDU - 4081 次小生成树之secondprim算法
原文：https://www.cnblogs.com/mzchuan/p/11828013.html