同样是看别人题解才明白的
题目大意——
话说秦始皇统一六国之后，打算修路。他要用n-1条路，将n个城市连接起来，并且使这n-1条路的距离之和最短。最小生成树是不是？不对，还有呢。接着，一个自称徐福的游方道士突然出现，他说他可以不消耗任何人力财力，使用法术凭空造一条路，路的长度无所谓，但是只能造一条。那么问题来了，徐福希望将两座人口数最多的城市连接起来，而秦始皇希望将最长的路修好。最后折中了一下， 将A/B最大的一条路用法术修出来。其中A是两座城市的人口和，B是除了用法术修的路以外，其它需要修建的路，也就是耗费人力财力修建的路。
输入：
第一行一个整数t，表示共有t组数据。
接下来一行一个整数n，表示有n个城市。
接下来n行，每行包括三个数x, y, p，表示这个城市横纵坐标以及人口数。
输出：A/B。
简单总结如下：
共有n个节点。有n*(n-1)/2条边。每个节点有一个点权vi，每条边有一条边权ek。要求的是(vi+vj)/(e-ek),其中e表示形成的树的边权之和，ek表示法术修成的边的边权，vi, vj表示法术修成的边所连接的两节点的权值。
虽然不能直接用最小生成树，但是可以确定，解题方法和最小生成树有关。
可以证明，用法术修成的边有两种情况，1. 在最小生成树上；2. 在最小生成树外。
1. 如果在最小生成树上，那么ek的值就是这条边的值，此时只要将这条边的的值从树的边权之和中删除即可。
2. 如果在最小生成树外，那么此时树上会形成一个环，我们需要将这个环上除了法术形成的边以外的一条边删除，删除的这条边就是ek，为了使(e-ek)尽可能小，那么删除的这条边需要尽可能大。因此，我们需要记录每条路径上的最长边。
无论哪种情况，vi, vj都是我们增添的那条边的两个端点。
附上记录每条路径最长边的代码——
因为使用的是prim算法，所以使每次循环后选择的新边与过去这条路径上的最长边比较。因为每条路径都是从一条边开始扩展的，因此，可以保证每次的新边的上一条边的记录都是最长边。
为此还需要记录新边的出发点，即，是从哪个点找到新点。类似于父节点与子节点的关系。
int pre[N]; //记录新点的父节点 void prim()
{
memset(path, , sizeof(path));
memset(vis, , sizeof(vis));
memset(used, , sizeof(used));
for(int i = ; i < n; i++)
{
dis[i] = mp[][i];
pre[i] = ; //由于是从0号节点开始的，所以所有节点的父节点初始为0号
}
vis[] = ;
for(int i = ; i < n; i++)
{
int k = -;
for(int j = ; j < n; j++)
if(!vis[j] && (k == - || dis[j] < dis[k])) k = j;
if(k == -) break; used[k][pre[k]] = used[pre[k]][k] = ; //表示此边在最小生成树上
vis[k] = ;
B += mp[pre[k]][k]; for(int j = ; j < n; j++)
{
if(vis[j] && j != k) path[j][k] = path[k][j] = max(path[j][pre[k]], dis[k]);//核心，用来记录路径上的最长边
if(!vis[j] && dis[j] > mp[j][k])
{
dis[j] = mp[j][k];
pre[j] = k; //更新新节点的父节点
}
}
}
}
此时，有两种选择，一种是枚举边，一种是枚举点。我使用的是枚举点的方法。
使用很简单的dp，更新输出结果为所用状态中的最大值即可——每次枚举无偿添加的边的两个端点，然后按照上面所述的1或2进行。
代码如下——
double ans = -;
for(int i = ; i < n; i++)
{
for(int j = ; j < n; j++)
{
if(i != j)
{
if(used[i][j]) ans = max(ans, (cost[i]+cost[j])/(B-mp[i][j])); //如果枚举的两个点的边在生成树上，则B减去那条边的权
else ans = max(ans, (cost[i]+cost[j])/(B-path[i][j])); //如果不在生成树上，则减去那条添加的边所形成的环中此边以外的最长边。
}
}
}
但是这个dp可以进行优化。
证明：最佳结果中，两个点中一定有一个点的点权是最大点权。
之前我们在逻辑上是先添加一条边，然后判断这条边是否在最小生成树上，然后删边。此时我们逆过来推，先删边。
在删掉任意一条边后，最小生成树T变成了两个子树T1, T2。可以得到条件：具有最大点权的点肯定在T1或T2上。
此时，由于已经删除了一条边，所以B为定值。因此，只需要使A的值尽量大，即可获得最佳答案。因此，我们分别选择两棵子树上具有最大点权的点连接。因此，我们肯定会选择到所有点中，具有最大点权的点。
根据这个结论，我们可以确定一个点，即最大点权的点。如此，将上面的双重循环中的一重循环去掉，变成单重循环的dp。
但此时我们需要在输入时记录点权最大的点。
代码如下——
double ans = -;
for(int i = ; i < n; i++)
{
if(i != mk) //mk为点权最大的点
{
if(used[i][mk]) ans = max(ans, (cost[i]+cost[mk])/(B-mp[i][mk]));
else ans = max(ans, (cost[i]+cost[mk])/(B-path[i][mk]));
}
}
完整代码如下——
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int N = ; int pre[N]; //记录新点的父节点
double mp[N][N]; //记录距离的地图
double path[N][N]; //记录路径中的最长边
double node[N][]; //记录节点坐标
double cost[N]; //记录节点的权值
double dis[N]; //prim中记录最小生成树的每条边权
bool vis[N], used[N][N];//记录某节点是否在最小生成树上，某边是否在最小生成树上
int n, t;
double B; double getdis(double x1, double y1, double x2, double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
} void prim()
{
memset(path, , sizeof(path));
memset(vis, , sizeof(vis));
memset(used, , sizeof(used));
for(int i = ; i < n; i++)
{
dis[i] = mp[][i];
pre[i] = ; //由于是从0号节点开始的，所以所有节点的父节点初始为0号
}
vis[] = ;
for(int i = ; i < n; i++)
{
int k = -;
for(int j = ; j < n; j++)
if(!vis[j] && (k == - || dis[j] < dis[k])) k = j;
if(k == -) break; //原谅这个吧，其实prim算法中不需要这个的，因为prim算法固定循环n-1次，但是我经常会写成n次，并因此爆RE，因此，我就加个这个，保证它在第n次直接跳出来，不执行下面的东西…… used[k][pre[k]] = used[pre[k]][k] = ; //表示此边在最小生成树上
vis[k] = ;
B += mp[pre[k]][k]; for(int j = ; j < n; j++)
{
if(vis[j] && j != k) path[j][k] = path[k][j] = max(path[j][pre[k]], dis[k]);//核心，用来记录路径上的最长边
if(!vis[j] && dis[j] > mp[j][k])
{
dis[j] = mp[j][k];
pre[j] = k; //更新新节点的父节点
}
}
}
} int main()
{
// freopen("test.txt", "r", stdin);
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
B = ;
double maxn = -;
int mk;
for(int i = ; i < n; i++)
{
scanf("%lf%lf%lf", &node[i][], &node[i][], &cost[i]);
if(cost[i] > maxn)
{
maxn = cost[i];
mk = i;
}
}
for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
mp[i][j] = getdis(node[i][], node[i][], node[j][], node[j][]);
prim();
double ans = -;
/*
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i != j)
{
if(used[i][j]) ans = max(ans, (cost[i]+cost[j])/(B-mp[i][j])); //如果枚举的两个点的边在生成树上，则B减去那条边的权
else ans = max(ans, (cost[i]+cost[j])/(B-path[i][j])); //如果不在生成树上，则减去那条添加的边所形成的环中此边以外的最长边。
}
}
}
*/
for(int i = ; i < n; i++)
{
if(i != mk) //mk为点权最大的点
{
if(used[i][mk]) ans = max(ans, (cost[i]+cost[mk])/(B-mp[i][mk]));
else ans = max(ans, (cost[i]+cost[mk])/(B-path[i][mk]));
}
}
printf("%.2lf\n", ans);
}
return ;
}
这个其实我也半懂不懂的，哪位巨巨看见什么错误恳请指出来，弱弱这厢有礼了……