#include<iostream>
#include<cstdio>
#include<memory.h>
#define MAX 10000
using namespace std;
int n,low[100],G[100][100],visited[100];
int PRIM()
{
int i,j,min,pos=1,result=0;
memset(visited,0,sizeof(visited));
for(i=1;i<=n;i++)
if(i!=pos)
low[i]=G[pos][i];
for(i=1;i<=n;i++)
{
min=MAX;
for(j=1;j<=n;j++)
if(visited[j]==0 && min>low[j])
{min=low[j];pos=j;}
visited[pos]=1;
result+=min;
for(j=1;j<=n;j++)
if(visited[j]==0 && low[j]>G[pos][j])
low[j]=G[pos][j];
}
return result;
}
int main()
{
int i,j,degree,cost;
char vertex;
while(cin>>n)//
{
if(n==0) break;
//for(int i=1;i<=n;i++) vertices[i]=i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
G[i][j]=MAX;
// for(int i=0;i<num;i++) visited[i]=false;
for(i=1;i<=n-1;i++)
{
cin>>vertex>>degree;
for(j=0;j<degree;j++)
{
cin>>vertex>>cost;
G[i][vertex-'A'+1]=cost;
G[vertex-'A'+1][i]=cost;
}
}
cout<<PRIM()<<endl;
}
return 0;
}
在输入的地方 ，老搞错 ，最后参考了别人的代码，值得注意
/*
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
216
3
A 2 B 10 C 40
B 1 C 20
30
0
Press any key to continue
*/
/*
int main()//ÓдíÎó »¹Ã»ÕÒµ½
{
int i,j,n,a,b,num,value,ans;
char s[100],space;
while(cin>>n)//while(scanf("%d",&n)!=EOF && n!=0)
{
getchar();
if(n==0) break;
//memset(G,MAX,sizeof(G));
for(i=1;i<100;i++)
for(j=1;j<100;j++)
G[i][j]=MAX;
for(i=1;i<n;i++)
{
scanf("%c%c%d",&a,&space,&num);
//printf("%c*** %d\n",a,num);
getchar();//ÎüÊջسµ»»ÐÐ
a=(char)a-'A'+1;
printf("%d*** %d\n",a,num);
for(j=1;j<=num;j++)
{
scanf("%c%c%d",&b,&space,&value);
getchar();
b=(char)b-'A'+1;//wrong:b-='A'+1 or b=b-'A'+1
printf("%d-%d:%d\n",a,b,value);
G[a][b]=G[b][a]=value;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(G[i][j]==MAX)
printf("~ ");
else
printf("%d ",G[i][j]);
cout<<endl;
}
ans=PRIM();
printf("%d\n",ans);
}//********while
return 0;
}
*/
/*
int main()
{
int i,j,num,a,b,v;
memset(G,MAX,sizeof(G));
printf("ÇëÊäÈ붥µãÊýºÍ±ßÊý£º");
scanf("%d %d",&n,&num);
for(i=1;i<=num;i++)
{
scanf("%d %d %d",&a,&b,&v);
G[a][b]=G[b][a]=v;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(G[i][j]==MAX)
printf("~ ");
else
printf("%d ",G[i][j]);
cout<<endl;
}
int ans=PRIM();
printf("%d\n",ans);
return 0;
}
/*
?????????:7 12
1 2 12
1 6 16
1 7 14
2 3 10
2 6 7
3 4 3
3 5 5
3 6 6
4 5 4
5 6 2
5 7 8
6 7 9
36
Press any key to continue
?????????:9 12
1 2 12
1 9 25
2 3 10
2 8 40
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 35
~ 12 ~ ~ ~ ~ ~ ~ 25
12 ~ 10 ~ ~ ~ ~ 40 8
~ 10 ~ 18 ~ ~ 55 ~ ~
~ ~ 18 ~ 44 ~ ~ ~ ~
~ ~ ~ 44 ~ 60 38 ~ ~
~ ~ ~ ~ 60 ~ ~ ~ ~
~ ~ 55 ~ 38 ~ ~ 35 ~
~ 40 ~ ~ ~ ~ 35 ~ 35
25 8 ~ ~ ~ ~ ~ 35 ~
216
Press any key to continue */