zoj1203:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1203
题意：给定平面上Ｎ个城市的位置，计算连接这Ｎ个城市所需线路长度总和的最小值
题解：每两个点之间建一条边，然后求这一棵最小生成树。
1 #include<cstring> 2 #include<cstdio> 3 #include<algorithm> 4 #include<iostream> 5 #include<cmath> 6 using namespace std; 7 int n,pa[102],cnt,num;//分别记录点的个数 ，并查集，边的个数，以及处理的边的个数 8 struct Node{ 9 double x; 10 double y; 11 }node[102];//记录每个点 12 struct Edge{ 13 int u; 14 int v; 15 double w; 16 bool operator<(const Edge &a)const{ 17 return w<a.w;} 18 }edge[10000];//记录每一条边，以及定义排序规则 19 void UFset(){ 20 for(int i=1;i<=n;i++) 21 pa[i]=-1; 22 }//初始化 23 int Find(int x){//查找 24 int s; 25 for(s=x;pa[s]>=0;s=pa[s]); 26 while(s!=x){ 27 int temp=pa[x]; 28 pa[x]=s; 29 x=temp; 30 }//路径压缩，便于后面的查找 31 return s; 32 } 33 void Union(int R1,int R2){//合并，把个数的集合作为子树加到另一棵树上 34 int r1=Find(R1); 35 int r2=Find(R2); 36 int temp=pa[r1]+pa[r2]; 37 if(pa[r1]>pa[r2]){ 38 pa[r1]=r2; 39 pa[r2]=temp; 40 } 41 else{ 42 pa[r2]=r1; 43 pa[r1]=temp; 44 } 45 } 46 double dist(Node a,Node b){//计算每两个点之间距离 47 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 48 } 49 double kruska(){//克鲁斯卡尔算法 50 UFset();//初始化 51 num=0; 52 double sum=0.0; 53 for(int i=0;i<cnt;i++){ 54 int u=edge[i].u; 55 int v=edge[i].v; 56 if(Find(u)!=Find(v)){ 57 sum+=edge[i].w; 58 num++; 59 Union(u,v); 60 } 61 if(num>=n-1)break; 62 } 63 return sum; 64 } 65 int main(){ 66 int t=0; 67 while(~scanf("%d",&n)&&n){ 68 cnt=0;//初始化 69 for(int i=1;i<=n;i++) 70 scanf("%lf%lf",&node[i].x,&node[i].y);//存边 71 for(int i=1;i<=n;i++){ 72 for(int j=i+1;j<=n;j++){ 73 edge[cnt].u=i; 74 edge[cnt].v=j; 75 edge[cnt++].w=dist(node[i],node[j]); 76 } 77 }//建边，每两个点之间建一条边 78 sort(edge,edge+cnt);//排序 79 if(t)printf(" "); 80 printf("Case #%d: ",++t); 81 printf("The minimal distance is: %.2f ",kruska()); 82 } 83 }