#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <math.h>
using namespace std;
#define MAXN 105
#define MAXM 5050
double X[MAXN],Y[MAXN];//用来存储x,y的坐标，其他关于坐标的运算可以模仿
int i,n,j,m,mi,x,y;//循环变量,frist i defined it in main()
double sum=0.0;//总权值
struct edge
{
int u,v;//顶点
double w;//权值，注意类型
}edges[MAXN];
int parent[MAXN];
int cmp(const void *a,const void *b)
{
// return (*(edge *))我想用另种方法
edge aa=*(const edge *)a;edge bb=*(const edge *)b;
if (aa.w>bb.w)
return 1;
else
return -1;
}
void UFset()//初始化
{
for(i=0;i<=mi;i++)
parent[i]=-1;
}
int Find(int x)//查找并返回节点x所属集合的根节点
{
int s=x;
for(;parent[s]>=0;s=parent[s])
;
while(s!=x)//优化方案——压缩路径，使后续查找更加方便，但为什么呢
{
parent[x]=s;
x=s;
}
return s;
}
void Union(int R1,int R2)
{
int r1=Find(R1),r2=Find(R2);// r1,r2分别为根节点
int tmp=parent[r1]+parent[r2];
if(parent[r1]>parent[r2])//优化方案，路径加权
{
parent[r1]=r2;parent[r2]=tmp;
}
else
{
parent[r2]=r1;parent[r1]=tmp;
}
}
void kruskal()
{
int num=0;
//int u,v;
UFset();
for(i=0;i<mi;i++)
{
x=edges[i].u;y=edges[i].v;
if(Find(x)!=Find(y))
{
//printf("%d %d",x,y);
sum+=edges[i].w;
num++;
Union(x,y);
}
if(num>=n-1)
break;
}
}
int main()
{
// freopen("in.txt","r",stdin);
// int n;//测试数据的个数
double d;//可以不要了
//int m=0,mi;//边的标志,中间变量
int kcase=1;
while(1)
{
cin>>n;
if(n==0)
break;
//输入各个城市的坐标
for(i=0;i<n;i++)
scanf("%lf%lf",&X[i],&Y[i]);//这一句关键去了，没有%lf不读数据
int m=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
//scanf("%f%f",&x,&y);自己第一次写的
//两点之间的距离
d=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
edges[m].u=i;
edges[m].v=j;
edges[m].w=d;
m++;
}
}
mi=m;//我先自己试试，还是用这个吧，比较好用
qsort(edges,mi,sizeof(edges[0]),cmp);
sum=0.0;
kruskal();
// for(i=0;i<mi;i++)
// printf("%d-->%d=%0.2f\n",edges[i].u,edges[i].v,edges[i].w);
if(kcase>1)
cout<<endl;
printf("Case #%d:\n",kcase);
printf("The minimal distance is: %0.2f\n",sum);
kcase++;
}
return 0;
}原文：http://blog.csdn.net/yuzibo747/article/details/19019001