題意：
秦始皇要修建連通所有城市的路，一共有N個點以及各個點的坐标和人口。修建很多條路使N個城市連通，但是可以使其中一條路的修建費用為0。在修建費用最小的前提下，使得A/B最大。A指費用為0的路所連通的兩個城市的人口和，B指除修建費用為0的路之外的是以路之和。
解題思路：因為要是整體的修建費用最小，必定要求他的最小生成樹。但是可以使生成樹中的一條邊的費用為0，這樣就不能簡單的光求最小生成樹。因為可以使連接配接某兩個城市的路修建費用為0，是以可以枚舉所有兩個城市的組合。這樣A的值就固定下來了，為了使得A/B最大。則需要删去這兩個城市的連通路徑中最長的邊，使得B值越小。因為在這兩個城市直接連邊是不需要費用的。這樣的話就和求次小生成樹的算法有點像了。一開始把問題像的簡單了，是以直接用了kruskal。但是求次小生成樹還是prime算法比較友善。
這道題基本就是次小生成樹的模闆題，模闆代碼基本沒怎麼改
這裡是關于次小生成樹的介紹：http://blog.csdn.net/qq_31607947/article/details/77563793
看别人的代碼蠻複雜，實際上就是 一次prim同時記錄每兩個點在樹上的邊中最大的那條，然後對于每兩個點周遊，删邊加邊
double坑了我好幾次wa
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn = 1011;
const double inf = 0x3f3f3f3f;
double Map[maxn][maxn];
double Max[maxn][maxn];
int pre[maxn];
double dis[maxn];
int people[maxn],x[maxn],y[maxn];
bool vis[maxn];
double prim(int n)
{
double ans = 0;
memset(vis, false, sizeof(vis));
memset(Max, 0, sizeof(Max));
for (int i = 2; i <= n; i++)
{
dis[i] = Map[1][i];
pre[i] = 1;
}
pre[1] = 0;
dis[1] = 0;
vis[1] = true;
for (int i = 2; i <= n; i++)
{
double min_dis = inf;
int k;
for (int j = 1; j <= n; j++)
{
if (!vis[j] && min_dis > dis[j])
{
min_dis = dis[j];
k = j;
}
}
ans += min_dis;
vis[k] = true;
for (int j = 1; j <= n; j++)
{
if (vis[j]&&j!=k)
Max[j][k] = Max[k][j] = max(Max[j][pre[k]], dis[k]);
if (!vis[j] && dis[j] > Map[k][j])
{
dis[j] = Map[k][j];
pre[j] = k;
}
}
}
return ans;
}
double smst(int n, double min_ans)
{
double ans = 0;
for (int i = 1; i <= n; i++)//枚舉最小生成樹之外的邊
for (int j = i + 1; j <= n; j++)
ans = max(ans, (people[i]+people[j])/((min_ans-Max[i][j])*1.0));
return ans;
}
int main()
{
int T, n;
scanf("%d", &T);
while (T--)
{
scanf("%d",&n);
for (int i = 1; i <=n; i++)
scanf("%d %d %d", &x[i], &y[i], &people[i]);
for (int i = 1;i<=n;i++)
for(int j=i;j<=n;j++)
Map[i][j]=Map[j][i]=sqrt(double((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]- y[j])));
double ans = prim(n);
printf("%.2lf\n",smst(n, ans));
}
return 0;
}
/*****************
本來準備放棄了回去沒想到臨走前改了double就過了
昨晚就睡了四個小時希望一會可以早早的睡着，最近失眠有點重