HDU 1162 Eddy's picture

这个题目也是典型的最小生成树算法，跟之前的那个题目是差不多的，也就是说：给你n个二维平面点，
让你添加适当的边，使得所有的点都在同一个联通分支上，也就是说任何点之间都有路径可以到达。
问题规模不大，直接用矩阵存数据，利用prim 算法就可以搞定。此时任意两点之间的“权值”就是
两点之间的距离。  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

补充：软件开发 , C语言 ,

上一个：HDU 1102 Constructing Roads
下一个：HDU 1116 Play on Words