频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
HDU 1162 Eddy's picture
2070-01-01 08:33:31           
收藏   我要投稿

这个题目也是典型的最小生成树算法,跟之前的那个题目是差不多的,也就是说:给你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

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:HDU 1116 Play on Words
下一篇:HDU 1102 Constructing Roads
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站