這題是典型的Minimum Spanning Tree,我用Prims Algorithm。
//ignore header files
#define dis(p1,p2) sqrt(((p1.x-p2.x)*(p1.x-p2.x))+((p1.y-p2.y)*(p1.y-p2.y)))
struct point{
double x,y;
int num;
point(double a,double b,int c){
x = a;
y = b;
num = c;
}
};
struct Edge{
int n;
double dis;
Edge(int a,double b){
n = a;
dis = b;
}
};
int main(int argc, char const* argv[])
{
int m;
while(scanf("%d",&m) != EOF){
for(int k = 0;k<m;k++){
int n;
double sum = 0;
bool visit[105];
scanf("%d",&n);
vector<Edge> G[105];
double d[105];
for(int i = 0;i<n;i++){
d[i] = 1e9;
visit[i] = 0;
}
vector<point> v;
for(int i = 0;i < n;i++){
double x,y;
scanf("%lf %lf",&x,&y);
v.push_back(point(x,y,i));
}
for(size_t i = 0;i<v.size()-1;i++)
for(size_t j = i+1;j<v.size();j++){
double w = dis(v[i],v[j]);
G[v[i].num].push_back(Edge(v[j].num,w));
G[v[j].num].push_back(Edge(v[i].num,w));
}
d[0] = 0;
for(int i = 0;i<n;i++){
int a = -1;
int min = 1e9;
for(int j = 0;j<n;j++){
//找離MST最近的點
if(!visit[j] && d[j]<min){
a = j;
min = d[j];
}
}
if(a == -1)
break;
visit[a] = true;
//抓到新的點,把MST到該點的距離加到sum中
sum = sum+d[a];
//檢查該點的鄰居
for(size_t j = 0;j<G[a].size();j++){
int b = G[a][j].n;
if(!visit[b] && G[a][j].dis<d[b]){
//更新此點到MST的距離
d[b] = G[a][j].dis;
}
}
}
if(k == 0)
printf("%.2lf\n",sum);
else
printf("\n%.2lf\n",sum);
}
}
return 0;
}