zoj1203 Swordfish ——最小生成树入门题

zoj1203 Swordfish ——最小生成树入门题_Kruscal算法

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=203

题目大意：

　　给定N个点的坐标，求经过这N个点的路线长度总和的最小值。

题目思路：

　　求出任意两点之间的距离，然后就是最小生成树。

　　写的过程中还是遇到了三个问题，有一个局部变量没有初始化；没有把边按照权值排序；另外就是没有看输出，每两个case之间有一个空行。这里有一个十分常见的问题，就是最后一个case后面没有空行。否则会PE。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <stack>
 7 #include <queue>
 8 #include <map>
 9 #include <set>
10 #include <vector>
11 #include <cmath>
12 #include <algorithm>
13 #define lson l, m, rt<<1
14 #define rson m+1, r, rt<<1|1
15 using namespace std;
16 typedef long long int LL;
17 const int MAXN =  0x3f3f3f3f;
18 const int  MIN =  -0x3f3f3f3f;
19 const double eps = 1e-9;
20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
21   {1,1},{1,-1},{-1,-1}};
22 
23 typedef struct Edge {
24   int u, v; double w;
25   bool operator < (const Edge &other) const {
26     return w < other.w;
27   }
28 }Edge;
29 Edge edge[5000];
30 int parent[109];
31 int N, m;
32 double X[109], Y[109], sum;
33 void init() {
34   int i;
35   for (i = 0; i < N; ++i) parent[i] = -1;
36 }
37 int find(int x)
38 {
39   int s;
40   for (s = x; parent[s] >= 0; s = parent[s]) ;
41   while (s != x) {
42     int tmp = parent[x];
43     parent[x] = s;
44     x = tmp;
45   }
46   return s;
47 }
48 void Union(int R1, int R2)
49 {
50   int r1 = find(R1), r2 = find(R2);
51   int tmp = parent[r1] + parent[r2];
52   if (parent[r1] > parent[r2]) {
53     parent[r1] = r2; parent[r2] = tmp;
54   } else {
55     parent[r2] = r1; parent[r1] = tmp;
56   }
57 }
58 void kruscal()
59 {
60   int num = 0, u, v, i;
61   init();
62   for (i = 0; i < m; ++i) {
63     u = edge[i].u; v = edge[i].v;
64     if (find(u) != find(v)) {
65       sum += edge[i].w; num++;
66       Union(u, v);
67     }
68     if (num >= N - 1) break;
69   }
70 }
71 
72 int main(void){
73 #ifndef ONLINE_JUDGE
74   freopen("zoj1203.in", "r", stdin);
75 #endif
76   int c = 1;
77   while (1) {
78     scanf("%d", &N);
79     if (!N) break;
80     if (c != 1) printf("\n");
81     printf("Case #%d:\nThe minimal distance is: ", c);c++;
82     int i, j;
83     for (i = 0; i < N; ++i) {
84       scanf("%lf%lf", &X[i], &Y[i]);
85     }
86     int cnt = 0; double dis;
87     for (i = 0; i < N; ++i) {
88       for (j = i + 1; j < N; ++j) {
89         dis = sqrt( (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]) );
90         edge[cnt].u = i; edge[cnt].v = j; edge[cnt].w = dis; cnt++;
91       }
92     }
93     m = cnt; sum = 0.0;
94     sort(edge, edge + m);
95     kruscal(); printf("%.2f\n", sum);
96   }
97 
98   return 0;
99 }

　　写代码最重要的一点还是要认真，变量初始化神马的，大于号小于号神马的，一些关键步骤不要漏掉，这些东西都要注意。细心一点。