問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1251http://acm.pku.edu.cn/JudgeOnline/problem?id=1258思路:
最簡單典型的最小生成樹，PRIM算法
參考算法導論
代碼(pku 1251):
1 /* MST problem */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 27
6 #define INF 0x7FFFFFFF
7 int num, min;
8 int adj[MAX_LEN][MAX_LEN];
9 int key[MAX_LEN], in[MAX_LEN];
10
11 void
12 init()
13 {
14 int i, j, k, dis;
15 char tmp[2], tmp1[2];
16 memset(adj, 0, sizeof(adj));
17 memset(in, 0, sizeof(in));
18 min = 0;
19 for(i=0; i<num; i++)
20 key[i] = INF;
21 for(i=0; i<num-1; i++) {
22 scanf("%s %d", tmp, &k);
23 for(j=0; j<k; j++) {
24 scanf("%s %d", tmp1, &dis);
25 adj[tmp[0]-'A'][tmp1[0]-'A'] = dis;
26 adj[tmp1[0]-'A'][tmp[0]-'A'] = dis;
27 }
28 }
29 }
30
31 void
32 prim()
33 {
34 int i, j, k, cur;
35 /* start from vertex 'A' */
36 in[0] = 1;
37 for(i=1; i<num; i++)
38 if(adj[0][i])
39 key[i] = adj[0][i];
40 for(i=1; i<num; i++) { /* num-1 vertex left */
41 cur = INF;
42 for(j=0; j<num; j++) {
43 if(!in[j] && key[j]<cur) {
44 cur = key[j];
45 k = j;
46 }
47 }
48 min += cur;
49 in[k] = 1;
50 for(j=0; j<num; j++) {
51 if(adj[k][j]) {
52 if(!in[j] && adj[k][j]<key[j])
53 key[j] = adj[k][j];
54 }
55 }
56 }
57 }
58
59 int
60 main(int argc, char **argv)
61 {
62 while(scanf("%d", &num)!=EOF && num) {
63 init();
64 prim();
65 printf("%d\n", min);
66 }
67 }