频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
HDU 1301 Jungle Roads
2011-07-18 16:14:43           
收藏   我要投稿

这个题目的意思就是说给你n个相关点,用A - I 来表示,然后给出n-1行,第 i 行表示从点 i 到其他点的相关信息。
在给出的map的基础上,要求选择适当的路线,使得所有给出的点都能够到达任意其他点,问题规模不大,直接矩阵
存储,利用prim 算法搞定。  1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<iostream>
 5 using namespace std;
 6
 7 const int MAX = 0x7ffffff;
 8 int map[27][27], MIN, v[27], n, dis, m, sum, flag;
 9 // map[i][j] 表示点 i 到点 j 的距离
10 char cx, cy;
11
12 void Reset(int n)
13 {
14      map[n][n];
15      memset(map, 0 ,sizeof(map));
16      for (int i=0; i<n-1; i++)
17      {
18          cin >> cx >> m;
19          for (int j=0; j<m; j++)
20          {
21              cin >> cy >> dis;
22              map[cx-'A'][cy-'A'] = map[cy-'A'][cx-'A'] =dis;
23              //注意下标和字符之间的转换
24          }
25      }
26     
27      for (int i=0; i<n; i++)
28      {
29          for (int j=0; j<n; j++)
30          {
31              if (map[i][j] == 0)map[i][j] = MAX;
32          }
33      }
34     
35 }
36
37 int MinTree(int n)
38 {// prim算法
39     v[n];
40     memset(v, 0, sizeof(v));
41     v[0] = 1;
42     sum = 0;
43     for (int i=1; i<n; i++)
44     {
45         MIN = MAX;
46         for (int j=0; j<n; j++)
47         {
48             if (!v[j] && map[0][j] < MIN)
49             {
50                MIN = map[0][j];
51                flag = j;
52             }
53         }
54         sum += MIN;
55         v[flag] = 1;
56         for (int j=0; j<n; j++)
57         {
58             if (!v[j] && map[0][j] > map[flag][j])
59             {
60                map[0][j] = map[flag][j];
61             }
62         }
63     }
64     printf("%d\n",sum);
65 }
66
67 int main()
68 {
69     while (scanf("%d", &n), n)
70     {
71           Reset(n);
72           MinTree(n);
73     }
74     return 0;
75 }
76

点击复制链接 与好友分享!回本站首页
相关TAG标签 HDU Jungle Roads
上一篇:点在三角形内之二 (三维坐标系1)
下一篇:HDU 1233 还是畅通工程
相关文章
图文推荐
点击排行

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

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