Swordfish

zoj1203:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1203

题意：给定平面上Ｎ个城市的位置，计算连接这Ｎ个城市所需线路长度总和的最小值
题解：每两个点之间建一条边，然后求这一棵最小生成树。

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 using namespace std;

 int n,pa[],cnt,num;//分别记录点的个数 ，并查集，边的个数，以及处理的边的个数

 struct Node{

     double x;

     double y;

 }node[];//记录每个点

 struct Edge{

     int u;

     int v;

     double w;

     bool operator<(const Edge &a)const{

         return w<a.w;}

 }edge[];//记录每一条边，以及定义排序规则

 void UFset(){

     for(int i=;i<=n;i++)

       pa[i]=-;

 }//初始化

 int Find(int x){//查找

     int s;

     for(s=x;pa[s]>=;s=pa[s]);

     while(s!=x){

         int temp=pa[x];

         pa[x]=s;

         x=temp;

     }//路径压缩，便于后面的查找

     return s;

 }

 void Union(int R1,int R2){//合并，把个数的集合作为子树加到另一棵树上

     int r1=Find(R1);

     int r2=Find(R2);

     int temp=pa[r1]+pa[r2];

     if(pa[r1]>pa[r2]){

         pa[r1]=r2;

         pa[r2]=temp;

     }

     else{

         pa[r2]=r1;

         pa[r1]=temp;

     }

 }

 double dist(Node a,Node b){//计算每两个点之间距离

     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

 }

 double kruska(){//克鲁斯卡尔算法

         UFset();//初始化

         num=;

     double sum=0.0;

     for(int i=;i<cnt;i++){

         int u=edge[i].u;

         int v=edge[i].v;

         if(Find(u)!=Find(v)){

             sum+=edge[i].w;

             num++;

             Union(u,v);

         }

         if(num>=n-)break;

     }

      return sum;

 }

 int main(){

       int t=;

    while(~scanf("%d",&n)&&n){

            cnt=;//初始化

      for(int i=;i<=n;i++)

         scanf("%lf%lf",&node[i].x,&node[i].y);//存边

      for(int i=;i<=n;i++){

         for(int j=i+;j<=n;j++){

                 edge[cnt].u=i;

                 edge[cnt].v=j;

                 edge[cnt++].w=dist(node[i],node[j]);

             }

         }//建边，每两个点之间建一条边

         sort(edge,edge+cnt);//排序

        if(t)printf("\n");

      printf("Case #%d:\n",++t);

      printf("The minimal distance is: %.2f\n",kruska());

     }

 }