POJ 1258 Agri-Net(最小生成树,基础)
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; #define M 110 #define inf 999999999 int mat[M][M]; int prim(int n,int sta) { int sum=0.0,dis[M]; int mark[M],i,j; for(i=0;i<n;i++) { dis[i]=mat[sta][i]; mark[i]=0; } mark[sta]=1; for(i=1;i<n;i++) { int minn=inf; int flag=-1; for(j=0;j<n;j++) { if(minn>dis[j]&&mark[j]==0) { flag=j; minn=dis[j]; } } mark[flag]=1; sum+=dis[flag]; for(j=0;j<n;j++) { if(dis[j]>mat[flag][j]) dis[j]=mat[flag][j]; } } return sum; } int main() { int t,i,j,n; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&mat[i][j]); } } printf("%d\n",prim(n,0)); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。