ZOJ1203 kruskal求最小生成树

题意：给定平面上的n个城市的位置，计算连接这n个城市所需路线长度总和的最小值
分析：直接运用kruskal算法求解。这题关键是建图。好好感受下面建图的思想。一开始我还是想按照以前最短路径那样建图，发现cmp的时候就出问题了。嗨，自己弱爆了。
View Code
  1 // I'm the Topcoder
  2 //C
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 #include <string.h>
  6 #include <ctype.h>
  7 #include <math.h>
  8 #include <time.h>
  9 //C++
 10 #include <iostream>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cstdlib>
 14 #include <cmath>
 15 #include <cstring>
 16 #include <cctype>
 17 #include <stack>
 18 #include <string>
 19 #include <list>
 20 #include <queue>
 21 #include <map>
 22 #include <vector>
 23 #include <deque>
 24 #include <set>
 25 using namespace std;
 26 
 27 //*************************OUTPUT*************************
 28 #ifdef WIN32
 29 #define INT64 "%I64d"
 30 #define UINT64 "%I64u"
 31 #else
 32 #define INT64 "%lld"
 33 #define UINT64 "%llu"
 34 #endif
 35 
 36 //**************************CONSTANT***********************
 37 #define INF 0x3f3f3f3f
 38 #define eps 1e-8
 39 #define PI acos(-1.)
 40 #define PI2 asin (1.);
 41 typedef long long LL;
 42 //typedef __int64 LL;   //codeforces
 43 typedef unsigned int ui;
 44 typedef unsigned long long ui64;
 45 #define MP make_pair
 46 typedef vector<int> VI;
 47 typedef pair<int, int> PII;
 48 #define pb push_back
 49 #define mp make_pair
 50 
 51 //***************************SENTENCE************************
 52 #define CL(a,b) memset (a, b, sizeof (a))
 53 #define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b))
 54 #define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c))
 55 
 56 //****************************FUNCTION************************
 57 template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); }
 58 template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; }
 59 template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; }
 60 
 61 // aply for the memory of the stack
 62 //#pragma comment (linker, "/STACK:1024000000,1024000000")
 63 //end
 64 
 65 #define maxn 100+10
 66 #define maxm 5000+10
 67 //边
 68 struct edge{
 69     int u,v;
 70     double w;
 71 }edges[maxm];//边的组数
 72 int parent[maxm];//parent[i]为顶点i所在集合对应的树中的根节点
 73 int n,m;
 74 double x[maxm],y[maxm];
 75 double sumweight=0;
 76 //double dis[maxm][maxm];
 77 
 78 //double juli(node x,node y){
 79 //    return sqrt((x.u-y.u)*(x.u-y.u)*(x.v-y.v));
 80 //}
 81 
 82 //初始化
 83 void UFset(){
 84     for(int i=0;i<n;i++){
 85         parent[i]=-1;
 86     }
 87 }
 88 
 89 int findset(int x){
 90     //return (parent[x]!=x?(parent[x]=findset(x)):x);
 91     int s;//查找的位置
 92     for(s=x;parent[s]>=0;s=parent[s]);
 93     while(s!=x){
 94         //优化方案：压缩路径，是后续的查找操作加速
 95         int tmp=parent[x];
 96         parent[x]=s;
 97         x=tmp;
 98     }
 99     return s;
100 }
101 
102 //合并
103 void Union(int R1,int R2){
104     int r1=findset(R1), r2=findset(R2);
105     int tmp=parent[r1]+parent[r2];
106     if(parent[r1]>parent[r2]){
107         parent[r1]=r2;
108         parent[r2]=tmp;
109     }
110     else {
111         parent[r2]=r1;
112         parent[r1]=tmp;
113     }
114 }
115 
116 //int cmp(const void*a,const void*b){
117 //    return *(double)
118 //}
119 int cmp(const void*a,const void* b){
120     edge aa=*(const edge*)a;
121     edge bb=*(const edge*)b;
122     if(aa.w>bb.w) return 1;
123     else return -1;
124 }
125 
126 void Krustral(){
127     int num=0;
128     int u,v;
129     UFset();
130     for(int i=0;i<m;i++){
131         u=edges[i].u;  v=edges[i].v;
132         if(findset(u)!=findset(v)){
133             //sumweight+=dis[u][v];
134             sumweight+=edges[i].w;
135             num++;
136             Union(u,v);
137         }
138         if(num>=n-1)  break;
139     }
140 }
141 
142 int main(){
143     double d;//两点之间的距离
144     int kase=1;
145     while(scanf("%d",&n)!=EOF){
146         if(n==0 ) break;
147         for(int i=0;i<n;i++){
148             //scanf("%lf%lf",&edges[i].u,&edges[i].v);
149             scanf("%lf%lf",&x[i],&y[i]);
150         }
151         int mi=0;//边的序号
152         for(int i=0;i<n;i++){
153             for(int j=i+1;j<n;j++){
154                 //dis[i][j]=juli(edges[i],edges[j]);
155                 d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
156                 edges[mi].u=i;  edges[mi].v=j;  edges[mi].w=d;
157                 mi++;
158 ;            }
159         }
160         m=mi;
161         qsort(edges,m,sizeof(edges[0]),cmp);
162         sumweight=0.0;
163         Krustral();
164         if(kase>1) printf("\n");
165         printf("Case #%d:\n",kase++);
166         printf("The minimal distance is: %0.2lf\n",sumweight);
167     }
168     return 0;
169 }