HDU 1301 Jungle Roads

这个题目的意思就是说给你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

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