hdu4081-次小生成树MST变形模板-Qin Shi Huang's National Road System

https://vjudge.net/problem/HDU-4081
给定你一个图，和每个点的坐标，问你建设n-1条路将它们链接起来后，可以减去其中一条边的花费，设其剩下的花费为B。而这条边对应的两个点的 点权大小为 A
要求A/B尽可能的大。。
思路：
这是用prim求次小生成树的方法。
维护path[][],作为表示i到在MST上的最长边。
并且 在一个最小生成树中，加一个边，一定构成环，然后你再减去一个。
那么他一定又是一个生成树（hiahia）。

这道题让维护去除一条 边后，去掉那个边的两个点的权值和生成树剩下的权值 比例尽可能的大。
所以 我们就想了一个办法，首先要分母尽可能的小，怎样让他最小呢。MST呀
那么 我们就是考虑 怎样在mst删除一个边，找到这样一个幸运的边了。
所以，直接枚举行么 emmmm我就是枚举写的，错了
因为发现样例1都没对。。（开始对了是完全的阴差阳错。。kruskal敲错了qwq）
那咋办捏。。
我们可以从 次小生成树中 学到一些东西（我tm之前不会啊qwq）
次小生成树的原理如图所示。
记录 mst中i-j路径中最长的边（废话，还有不在mst中的点么）
然后我们发现，次小生成树的诞生具有如此不可确定性，以至于每一对边都是有可能的。
所以我们 就要枚举每对边了。为了让其都有作为 次小的潜质，必须使其尽可能的小（。。。）
所以 我们就要 用类似dp的方法维护 那个Max数组了。
而维护的这个数组，正好为本题所用。。。。
（图中，蓝和绿两个点之间的红边如果替换他们再mst上 最大的边，那么就可能得到次小，枚举两两，次小比得qwq。）并且那个最大的边是不可能有好多的，树无环。

   #include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define INF 2147483647
#define N 1005
using namespace std;
/*
*/
double G[N][N],  minCost[N], pos[N][2], path[N][N], cost[N], ratio1, A, B;
int pre[N], vis[N], n;
bool used[N][N];
double Prim(){B=0;memset(vis, 0, sizeof(vis));memset(used, 0, sizeof(used));memset(path, 0, sizeof(path));vis[1]=1;for(int i=1; i<=n; ++i){minCost[i] = G[1][i];pre[i] = 1;}for(int i=1; i<n; ++i){int u=-1;for(int j=1; j<=n; ++j)if(!vis[j]){if(u==-1 || minCost[j]<minCost[u])u = j;}used[u][pre[u]]=used[pre[u]][u] = true;B += G[pre[u]][u];vis[u] = 1;for(int j=1; j<=n; ++j){if(vis[j]&&j!=u){path[u][j]=path[j][u]=max(path[j][pre[u]], minCost[u]);}if(!vis[j]){if(minCost[j]>G[u][j]){minCost[j] = G[u][j];pre[j] = u;}}}}return B;
}
int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);memset(G, 0, sizeof(G));for(int i=1; i<=n; ++i)scanf("%lf%lf%lf",&pos[i][0],&pos[i][1],&cost[i]);for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j)if(i!=j){G[i][j] = getDist(pos[i][0],pos[i][1],pos[j][0],pos[j][1]);}}Prim();ratio1 = -1;for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j)if(i!=j){ratio1 = max(ratio1, (cost[i]+cost[j])/(B-path[i][j]));}}printf("%.2f\n", ratio1);}return 0;
}