Problem:1258 | User: qq1203456195 | |
Memory: 208K | Time: 16MS | |
Language: C | Result: Accepted |
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 105 #define MAX 100005 int visited[N],closet[N],Metr[N][N]; int n; int prim() { int i,ms,next,sum,j; memset(visited,0,sizeof(visited)); for (i=0;i<n;i++) closet[i]=Metr[0][i]; visited[0]=1; sum=0; for (j=1;j<n;j++) { ms=MAX; for (i=0;i<n;i++) { if (!visited[i]&&closet[i]<ms) { ms=closet[i]; next=i; } } sum+=ms; visited[next]=1; for (i=0;i<n;i++) if (!visited[i]&&Metr[next][i]<closet[i]) closet[i]=Metr[next][i]; } return sum; } int main() { int i,j; while(scanf("%d",&n)!=EOF) { for (i=0;i<n;i++) for (j=0;j<n;j++) scanf("%d",&Metr[i][j]); printf("%d\n",prim()); } return 0; }
本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/04/15/2450739.html,如需转载请自行联系原作者