題目鏈接：http://poj.org/problem?id=2560 裸的最小生成樹，捉急的是他給的是每個(gè)點(diǎn)的x，y坐標(biāo)，所以需要重新建邊，因?yàn)槟承﹩栴}，CE好幾次，WA好幾次，語言要選擇C++，否則會(huì)WA，而且你還不知道怎么WA的
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 101
9 #define M 10000
10 int tot;
11 struct nn
12 {
13 double x, y;
14 }a[N];
15 struct ee
16 {
17 int u, v;
18 double w;
19 }e[M];
20 int p[N];
21 double dis(int x, int y)
22 {
23 double xx = a[x].x - a[y].x;
24 double yy = a[x].y - a[y].y;
25 double d = xx * xx + yy * yy;
26 return sqrt(d);
27 }
28 void init(int x, int y)
29 {
30 tot++;
31 e[tot].u = x;
32 e[tot].v = y;
33 e[tot].w = dis(x, y);
34 }
35 int find(int x)
36 {
37 return p[x] != x ? p[x] = find(p[x]) : x;
38 }
39 bool cmp(ee a, ee b)
40 {
41 return a.w < b.w;
42 }
43 int main()
44 {
45 int n;
46 int r1, r2;
47 double d;
48 while (cin >> n)
49 {
50 tot = 0;
51 d = 0;
52 memset(e, 0, sizeof(e));
53 memset(a, 0, sizeof(a));
54 for (int i = 1; i <= n; i++) p[i] = i;
55 for (int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].x, &a[i].y);
56 for (int i = 1; i <= n; i++)
57 for (int j = 1; j <= n; j++)
58 if (i != j)
59 init(i, j);
60 sort(e + 1, e + 1 + tot, cmp);
61 for (int i = 1; i <= tot; i++)
62 {
63 r1 = find(e[i].u); r2 = find(e[i].v);
64 if (r1 != r2)
65 {
66 p[r2] = r1;
67 d += e[i].w;
68 }
69 }
70 printf("%.2lf\n", d);
71 }
72 return 0;
73
|