Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5608 Accepted Submission(s): 1972
题目大意：给你n，表示城市个数，然后给你n个城市的坐标及该城市中的人口数量。让连接这n个城市用n-1条边连接，且距离和最短，距离越长花费越大。数字A表示，用魔法路连接的两个城市的人口的和，B表示除了该魔法路以外的其他路的长度和。求A/B的比率最小值是多少。魔法路没有路长。
解题思路：考虑让除了魔法路以外的路长和最小，那么我们可以从最小生成树中删除一条最长路径。枚举删除任意两点间的最长路，更新出最小比率。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
double cost[maxn][maxn];
struct Coor{
double x, y;
int peo;
}cors[maxn];
double distan(Coor a,Coor b){
double dx,dy;
dx = a.x - b.x;
dy = a.y - b.y;
return sqrt( dx*dx + dy*dy );
}
int vis[maxn], pre[maxn] ,used[maxn][maxn];
double maxcost[maxn][maxn], lowc[maxn];
double prim(int n){
memset(vis,0,sizeof(vis));
memset(used,0,sizeof(used));
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
maxcost[i][j] = 0;
}
}
// memset(maxcost,0,sizeof(maxcost));
// memset(lowc,0,sizeof(lowc));
double retsum = 0;
vis[0] = 1;
for(int i = 0; i < n; i++){
lowc[i] = cost[0][i];
pre[i] = 0;
}
for(int i = 1; i < n; i++){
int s = -1;
double minc = 1.0*INF;
for(int j = 0; j < n; j++){
if(!vis[j] && lowc[j] < minc){
minc = lowc[j];
s = j;
}
}
if(s == -1){
return -1;
}
retsum += minc;
int pa = pre[s];
vis[s] = 1;
for(int j = 0; j < n; j++){
if(vis[j]&&j != s){
maxcost[s][j] = maxcost[j][s] = max(maxcost[pa][j],cost[pa][s]);
}
}
used[s][pa] = used[pa][s] = 1;
for(int j = 0; j < n; j++){
if(!vis[j] && lowc[j] > cost[s][j]){
lowc[j] = cost[s][j];
pre[j] = s;
}
}
}
return retsum;
}
int main(){
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 0; i <=n; i++){
for(int j = 0; j <= n; j++){
cost[i][j] = 1.0*INF;
}
}
for(int i = 0; i < n; i++){
scanf("%lf%lf%d",&cors[i].x,&cors[i].y,&cors[i].peo);
for(int j = 0; j < i; j++){
cost[i][j] = cost[j][i] = distan(cors[i],cors[j]);
}
}
double mst = prim(n);
double maxr = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) continue;
int tmp = (cors[i].peo + cors[j].peo);
if(!used[i][j]){
maxr = max( maxr, (1.0*tmp)/(mst-maxcost[i][j]));
}else{
maxr = max(maxr,(1.0*tmp)/(mst - cost[i][j]));
}
}
}
printf("%.2lf\n",maxr);
}
return 0;
}
HDU 4081—— Qin Shi Huang's National Road System——————【次小生成树、prim】
原文：http://www.cnblogs.com/chengsheng/p/4924776.html