//最小生成树：Prim#include <stdio.h>#include <string.h>#define arraysize 28int dis[arraysize][arraysize];bool final[arraysize];int d[arraysize];int n;int maxData = 0x7fffffff;void Prim(){ int i; int j; int v; int min; int sum = 0; memset(final,0,sizeof(final)); for(i=1;i<n+1;++i) { d[i] = dis[1][i]; } final[1] = true; d[1] = 0; v =1; for(i=1;i<n;++i) { min = maxData; for(j=1;j<n+1;++j) { if(!final[j] && min>d[j] && d[j]<maxData) //别忘了判断是否小于最大值 { v = j; min = d[j]; } } sum += min; final[v] = true; for(j=1;j<n+1;++j) { if(!final[j] && d[j]>dis[v][j] && dis[v][j]<maxData) //别忘了判断是否小于最大值 d[j] = dis[v][j]; } } printf("%d\n",sum);}int main(){ //freopen("1.txt","r",stdin); int k; int cost; int i,j; char start[10],end[10]; while(scanf("%d",&n)!=EOF) { if(n==0) break; //初始化临界矩阵 for(i=1;i<n+1;++i) { for(j=1;j<n+1;++j) dis[i][j] = maxData; } for(i=1;i<n;++i) { //不要使用字符，直接读取字符串 scanf("%s%d",&start,&k); for(j=1;j<k+1;j++) { scanf("%s%d",&end,&cost); //将字符转换成数字，A的ASCII码65，双向的 dis[start[0]-64][end[0]-64] = cost; dis[end[0]-64][start[0]-64] = cost; } } Prim(); } return 0;}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/04/30/1725376.html
相关资源：数据结构—成绩单生成器