频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
HDU 1102 Constructing Roads
2011-07-19 10:43:02           
收藏   我要投稿

这个题目的意思就是说,给你一个有n个村庄的地图,map[i][j]表示从村庄 i 到村庄 j 的距离,然后给你
m 条已有道路,让你在这个基础上添加适当的道路,使得所有村庄之间都是联通的,求添加道路的最短距
离的值。 典型的最小生成树算法的运用。  1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4
 5 const int MAX = 0x7fffffff;
 6 int map[101][101], v[101], x, y, n, sum, flag, min;
 7
 8 void Reset(int n)
 9 {//根据 规模  n 的大小  ,建立 map!
10      for (int i=0; i<n; i++)
11      {
12          for (int j=0; j<n; j++)
13          {
14              scanf("%d", &map[i][j]);
15              if (i == j)map[i][j] = 0;
16          }
17      }
18      int m;
19      scanf("%d", &m);
20      for (int i=0; i<m; i++)
21      {
22          scanf("%d %d", &x, &y);
23          map[x-1][y-1] = map[y-1][x-1] = 0;
24      }
25 }
26 void MinTree()
27 {// 最小生成树算法
28      memset(v, 0, sizeof(v));
29      v[0] = 1;
30      sum = 0;
31      for (int i=1; i<n; i++)
32      {
33          min = MAX;
34          for (int j=0; j<n; j++)
35          {
36              if (!v[j] && map[0][j] < min)
37              {
38                 min = map[0][j], flag = j;
39              }
40          }
41          v[flag] = 1;
42          sum += min;
43          for (int j=0; j<n; j++)
44          {
45              if (!v[j] && map[0][j] > map[flag][j])
46              {
47                 map[0][j] = map[flag][j];
48              }
49          }
50      }
51      printf("%d\n", sum);
52 }
53
54 int main()
55 {
56     while (scanf("%d", &n) != EOF)
57     {
58           Reset(n);
59           MinTree();
60     }
61     return 0;
62 }

点击复制链接 与好友分享!回本站首页
相关TAG标签 HDU Constructing Roads
上一篇:HDU 1162 Eddy's picture
下一篇:Vczh Library++3.0之ManagedX语言检查类型的可见性
相关文章
图文推荐
点击排行

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

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