HDU 1301 Jungle Roads這個題目的意思就是說給你n個相關(guān)點(diǎn)，用A - I 來表示，然后給出n-1行，第 i 行表示從點(diǎn) i 到其他點(diǎn)的相關(guān)信息。
在給出的map的基礎(chǔ)上，要求選擇適當(dāng)?shù)穆肪€，使得所有給出的點(diǎn)都能夠到達(dá)任意其他點(diǎn)，問題規(guī)模不大，直接矩陣
存儲，利用
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] 表示點(diǎn) i 到點(diǎn) 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 //注意下標(biāo)和字符之間的轉(zhuǎn)換
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