不多说,用模板,注意?是没有访问到全部的点。
#include<stdio.h> #include<string.h> const int maxn = 110; #define INF 0xfffffff int map[maxn][maxn],lowcost[maxn],vis[maxn],n,m; int prim() { int i,j,k,mins,yes; int sum=0; for(i=1;i<=m;i++) lowcost[i] = map[1][i]; memset(vis,0,sizeof(vis)); vis[1]=1; for(;;) { mins=INF; yes=-1; for(j=1;j<=m;j++) { if(!vis[j] && lowcost[j] < mins) { mins=lowcost[j]; k=j; yes=1; } } if(yes==-1) break; sum+=mins; vis[k]=1; for(j=1;j<=m;j++) { if(!vis[j] && lowcost[j] > map[k][j]) lowcost[j] = map[k][j]; } } for(i=1;i<=m;i++) if(!vis[i]) return 0; return sum; } int main() { int i,j; int x,y,z; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0) break; for(i=1;i<=m;i++) { for(j=1;j<=m;j++) map[i][j]=INF,map[j][i]=INF; map[i][i]=0; } for(i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); if(z<map[x][y] ) map[x][y] = z; if(z<map[y][x]) map[y][x] = z; } int temp = prim(); if(temp ==0) printf("?\n"); else printf("%d\n",temp); } return 0; }