这个题目也是典型的最小生成树算法，跟之前的那个题目是差不多的，也就是说：给你n个二维平面点，
让你添加适当的边，使得所有的点都在同一个联通分支上，也就是说任何点之间都有路径可以到达。
问题规模不大，直接用矩阵存数据，利用prim 算法就可以搞定。此时任意两点之间的“权值”就是
两点之间的距离。? 1 #include
?2 #include
?3 #include
?4 #include
?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 23????? {
24????????? for (int j=i; 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 42????? {
43????????? min = MAX;
44????????? for (int j=0; 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 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 71?????????? {
72?????????????? scanf("%lf %lf", &point[i].x, &point[i].y);
73?????????? }
74?????????? Build();
75?????????? MinTree();
76???? }
77???? return 0;
78 }
79