HDU 1162 Eddy's picture

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, 0sizeof(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, 0sizeof(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 


posted on 2011-07-18 08:42 AK 阅读(1313) 评论(0)  编辑 收藏 引用 所属分类: 最小生成树和并查集


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

资源连接

搜索

最新评论

阅读排行榜

评论排行榜