题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4081
题意：有n个城市，秦始皇要修用n-1条路把它们连起来，要求从任一点出发，都可以到达其它的任意点。秦始皇希望这所有n-1条路长度之和最短。然后徐福突然有冒出来，说是他有魔法，可以不用人力、财力就变出其中任意一条路出来。
秦始皇希望徐福能把要修的n-1条路中最长的那条变出来，但是徐福希望能把要求的人力数量最多的那条变出来。对于每条路所需要的人力，是指这条路连接的两个城市的人数之和。
最终，秦始皇给出了一个公式，A/B，A是指要徐福用魔法变出的那条路所需人力， B是指除了徐福变出来的那条之外的所有n-2条路径长度之和，选使得A/B值最大的那条。
题解：就是次小生成树稍微改一下就行，这里只能用prim的次小生成树，由于边太多但是点还是1000。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
struct TnT {
int x , y , p;
}T[1010];
double lowcost[1010] , mmp[1010][1010] , maxpath[1010][1010] , cost[1010];
int pre[1010];
bool vis[1010][1010] , has[1010];
double prim(int n) {
lowcost[1] = 0;
pre[1] = 0;
memset(vis , false , sizeof(vis));
memset(has , false , sizeof(has));
has[1] = true;
for(int i = 2 ; i <= n ; i++) {
lowcost[i] = mmp[1][i];
pre[i] = 1;
}
double sum = 0;
for(int i = 2 ; i <= n ; i++) {
int pos = 0;
double MIN = 10000000000000.0;
for(int j = 1 ; j <= n ; j++) {
if(!has[j] && lowcost[j] < MIN) {
MIN = lowcost[j];
pos = j;
}
}
sum += MIN;
vis[pos][pre[pos]] = vis[pre[pos]][pos] = true;
has[pos] = true;
for(int j = 1 ; j <= n ; j++) {
if(has[j] && j != pos) {
maxpath[pos][j] = maxpath[j][pos] = max(maxpath[j][pre[pos]] , lowcost[pos]);
}
if(!has[j]) {
if(mmp[pos][j] < lowcost[j]) {
lowcost[j] = mmp[pos][j];
pre[j] = pos;
}
}
}
}
return sum;
}
double getlen(int a , int b) {
return sqrt((T[a].x - T[b].x) * (T[a].x - T[b].x) + (T[a].y - T[b].y) * (T[a].y - T[b].y));
}
int main() {
int t;
scanf("%d" , &t);
while(t--) {
int n;
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++) {
int u , v , p;
scanf("%d%d%d" , &u , &v , &p);
T[i].x = u , T[i].y = v , T[i].p = p;
cost[i] = 1.0 * p;
}
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++) {
mmp[i][j] = getlen(i , j);
}
}
double sum = prim(n);
double val = 0.0;
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++) {
if(i == j) continue;
if(!vis[i][j]) {
val = max(val , 1.0 * (cost[i] + cost[j]) / (sum - maxpath[i][j]));
}
else {
val = max(val , 1.0 * (cost[i] + cost[j]) / (sum - mmp[i][j]));
}
}
}
printf("%.2lf
" , val);
}
return 0;
}