这类题目做多了,简直就是水题。很直接的一个prim算法。
不必多解释。
#include<stdio.h> #include<string.h> const int Max=0xffffff; int main() { int i,j,n,k; int a[100][100],w[100]; while(~scanf("%d",&n)) { memset(a,0x3fff,sizeof(a)); memset(w,0x3fff,sizeof(w)); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); for(i=0;i<n;i++) w[i]=a[0][i]; w[0]=0; int sum=0; for(i=0;i<n-1;i++) { int min=Max; for(j=0;j<n;j++) if(w[j]&&w[j]<min) { min=w[j]; k=j; } sum+=min; w[k]=0; for(j=0;j<n;j++) if(a[k][j]<w[j]) { w[j]=a[k][j]; } } printf("%d\n",sum); } return 0; }