HDU 1162 Eddy's picture這個(gè)題目也是典型的最小生成樹算法，跟
之前的那個(gè)題目是差不多的，也就是說：給你n個(gè)二維平面點(diǎn)，
讓你添加適當(dāng)?shù)倪叄沟盟械狞c(diǎn)都在同一個(gè)聯(lián)通分支上，也就是說任何點(diǎn)之間都有路徑可以到達(dá)。
問題規(guī)模不大，直接用矩陣存數(shù)據(jù)，利用
prim 算法就可以搞定。此時(shí)任意兩點(diǎn)之間的“權(quán)值”就是
兩點(diǎn)之間的距離。
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<math.h>
4 #include<string.h>
5 const double MAX = 1000000000.0;
6 struct Point
7 {
8 double x, y;
9 }point[101];
10
11 double map[101][101];
12 int v[101], n;
13
14 double Dis(Point a, Point b)
15 {
16 return sqrt((a.x - b.x) * (a.x - b.x) +(a.y - b.y) * (a.y - b.y));
17 }
18
19 void Build()
20 {
21 memset(map, 0, sizeof(map));
22 for (int i=0; i<n; i++)
23 {
24 for (int j=i; j<n; j++)
25 {
26 if (i == j) map[i][j] = MAX;
27 else
28 {
29 map[j][i] = map[i][j] = Dis(point[i], point[j]);
30 }
31 }
32 }
33 }
34
35 void MinTree()
36 {
37 double sum = 0.0, min;
38 memset(v, 0, sizeof(v));
39 v[0] = 1;
40 int flag;
41 for (int i=1; i<n; i++)
42 {
43 min = MAX;
44 for (int j=0; j<n; j++)
45 {
46 if (!v[j] && map[0][j] < min)
47 {
48 min = map[0][j];
49 flag = j;
50 }
51 }
52 sum += min;
53 v[flag] = 1;
54 for (int j=0; j<n; j++)
55 {
56 if (!v[j] && map[0][j] > map[flag][j])
57 {
58 map[0][j] = map[flag][j];
59 }
60 }
61 }
62 printf("%.2lf\n",sum);
63 }
64 int main()
65 {
66 while (scanf("%d", &n)!= EOF)
67 {
68 map[n][n];
69 point[n];
70 for (int i=0; i<n; i++)
71 {
72 scanf("%lf %lf", &point[i].x, &point[i].y);
73 }
74 Build();
75 MinTree();
76 }
77 return 0;
78 }
79