次小生成树可由最小生成树换一条边得到
次小生成树，关键是求MaxVal数组：MaxVal[u][v]保存uv点之间在mst中的边最长的边的长度
1）先求一棵MST，利用Prim算法(只能Prim,因为Prim是一个一个收录点的)，且在求的时候求出MaxVal数组，
更新MaxVal方法如下：
prim算法中，已经加入生成树的点集合为W
? 往W新增点s时，设 u 属于W,且 s是被连接到W中的v点的，
? 则
? Max_val[v][s] = 边(v,s)的权
? Max_val[u][s] = Max( Max_val[v][s], Max_val[u][v])
这样将u，v之间的线段(非树边)代替u,v之间在mst上最长的边，就得到其中一种次小生成树了
2）枚举u，v点(非树边)，替换MaxVal[u][v]边，算出总权值，选最小的一种替换，就可以得到次小生成树了
示例模板如下：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=1000000000;
const int maxn=1000+5;
const double EPS=1e-6;
struct Point{int x,y,pop;Point(int x,int y):x(x),y(y){}
};
vector<Point> points;
struct Edge{int from,to;double w;Edge(int f,int t,double w):from(f),to(t),w(w){}bool operator < (const Edge& e) const {return w>e.w;}
};
double G[maxn][maxn];
double getdist(int i,int j){Point x=points[i],y=points[j];return hypot(x.x-y.x,x.y-y.y);
}
void getEdge(int n)
{for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){double d=getdist(i,j);G[i][j]=G[j][i]=d;}
}
double MaxVal[maxn][maxn];
double Prim(int n) //返回最小生成树的总权值
{memset(MaxVal,0,sizeof(MaxVal));vector<double> dist(n,INF);vector<bool> used(n,false);vector<int> mst;priority_queue<Edge> Q;double TotW=0; //mst的总权值 Q.push(Edge(0,0,0));while(mst.size()<n&&!Q.empty()){Edge e=Q.top(); Q.pop();while(used[e.to]&&!Q.empty()) e=Q.top(),Q.pop();if(used[e.to]) continue;TotW+=e.w;int s=e.to;int v=e.from;MaxVal[s][v]=MaxVal[v][s]=G[v][s];for(int i=0;i<mst.size();i++){int u=mst[i];MaxVal[u][s]=max(MaxVal[v][s],MaxVal[u][v]);MaxVal[s][u]=max(MaxVal[s][v],MaxVal[v][u]); //因为是无向边，所以MaxVal[u][v]=MaxVal[v][u] }used[s]=true; mst.push_back(s);for(int v=0;v<n;v++){if(v==s) continue;double w=G[s][v];if(!used[v]&&dist[v]>w){dist[v]=w;Q.push(Edge(s,v,w));}}}double ans=INF;for(int u=0;u<n;u++)for(int v=u+1;v<n;v++){double d=getdist(u,v);if(fabs(d-MaxVal[u][v])<EPS) continue; //树边 ans=min(ans,TotW-MaxVal[u][v]+d);}return ans;
}
int main()
{int T,n;cin>>T;while(T--){ int x,y;cin>>n;points.clear();for(int i=0;i<n;i++){cin>>x>>y;points.push_back(Point(x,y));}getEdge(n);printf("%.2lf\n",Prim(n));}return 0;
}