HDU Jungle Roads 1301 最小生成树、

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1301

题目大意：输入一个n，表示有n个村庄，然后下面是n-1行，每行开头有两个代表字母和数字，分别表示起始点和与其相同的村庄的个数。然后就是与其相同的村庄和道路长度，求最小连通值。

代码

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int map[30][30];
 5 int vis[30];
 6 int prim(int n)
 7 {
 8     int ans = 0;
 9     int d[30];
10     memset(vis,0,sizeof(vis));
11     int i,j,pos,min;
12 
13     vis[1] = 1;
14     for(i = 2;i <= n;i++)
15     d[i] = map[1][i];
16 
17     for(i =1;i < n;i++)
18     {
19         min = 0x7fffffff;
20         for(j = 2;j <= n;j++)
21         {
22             if(min > d[j] && !vis[j])
23             min = d[j],pos = j;
24         }
25 
26         ans += min;
27 
28         vis[pos] = 1;
29 
30         for(j = 2;j <= n;j++)
31         if(d[j] > map[pos][j] && !vis[j])
32         d[j] = map[pos][j];
33     }
34     return ans;
35 }
36 int main()
37 {
38     int n,i,j,m,count,val,ans;
39     char s[5],d[5];
40     while(scanf("%d",&n)&&n)
41     {
42         for(i = 1;i <= n;i++)
43         for(j = 1;j <= n;j++)
44         map[i][j] = 0x7fffffff;
45 
46         for(i = 0;i < n-1;i++)
47         {
48             scanf("%s %d",s,&count);
49             while(count--)
50             {
51                 scanf("%s %d",d,&val);
52                 map[s[0]-'A'+1][d[0]-'A'+1] = map[d[0]-'A'+1][s[0]-'A'+1] = val;
53             }
54         }
55         ans = prim(n);
56         printf("%d\n",ans);
57     }
58     return 0;
59 }