题目：
/************************************************************************//* hdu Jungle Roads 最小生成树 题目大意：最小生成树，题目很长，题意很简单就是最小生成树，prim算法模拟*//************************************************************************/#include#include #include #include #define MAX 0xfffffffconst int N = 30;int map[N][N];int vis[N];int n;void build_map(){ int t = n; char v,e; int num,len; for (int i = 0; i < n; i++) for (int j = i; j < n; j++) map[i][j] = map[j][i] = ((i==j)?0:MAX); while(--t) { getchar(); v = getchar(); scanf("%d",&num); while(num--) { getchar(); e = getchar(); scanf("%d",&len); map[v-'A'][e-'A'] = map[e-'A'][v-'A'] = len; } }}int prim(){ int t = n; int sum = 0; int min,k; vis[0] = 1; while(--t) { min = MAX; for(int i = 1; i < n; i++) { if (vis[i] != 1 && map[0][i] < min) { min = map[0][i]; k = i; } } vis[k] = 1; sum += min; for (int i = 1; i < n; i++) { if (vis[i] != 1 && map[k][i] < map[0][i]) map[0][i] = map[k][i]; } } return sum;}int main(){ while(scanf("%d",&n) && n != 0) { build_map(); memset(vis,0,sizeof(vis)); printf("%d\n",prim()); } return 0;}