这个我就不解释了 和dijkstra很像 两个只要懂了任何一个就可以A题 嘿嘿...
这个好处就是时间效率很高 嘿嘿 不需要并查集 一直递归了
代码如下:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define inf 0x3fffffff int N; int M; int visit[105]; int map[105][105]; int dis[105]; int prim() { for(int i=1;i<=N;i++) dis[i]=inf; dis[1]=0; for(int j=1;j<=N;j++) { int t=inf; int pos; for(int i=1;i<=N;i++) { if(!visit[i]&&t>dis[i]) { t=dis[i]; pos=i; } } visit[pos]=1; for(i=1;i<=N;i++) { if(!visit[i]&&dis[i]>map[pos][i]&&map[pos][i]!=0x3f3f3f3f) { dis[i]=map[pos][i]; } } } int temp=0; for(i=1;i<=N;i++) { temp+=dis[i]; } return temp; } int main() { while(scanf("%d",&N),N) { int a,b,val; memset(map,0x3f,sizeof(map)); memset(visit,0,sizeof(visit)); M=(N-1)*N/2; for(int i=1;i<=M;i++) { scanf("%d%d%d",&a,&b,&val); if(val<map[a][b]) { map[a][b]=val; map[b][a]=val; } } int ans=prim(); printf("%d\n",ans); } return 0; }