poj-1258 Agri-Net
http://poj.org/problem?id=1258
简单题
#include <iostream> #include <stdio.h> #include <math.h> #include <algorithm> #include <string.h> #define INF 10099990 using namespace std; int map[110][110],dis[110],v[110]; long long prim(int n) { int k; long long min,sum=0; memset(v,0,sizeof(v)); memset(dis,0,sizeof(dis)); for(int i=1;i<=n;i++) dis[i]=map[1][i]; v[1]=1; dis[1]=0; for(int i=2;i<=n;i++) { k=-1; min = INF; for(int j=1;j<=n;j++) if(!v[j]&&min>dis[j]) { k=j; min=dis[j]; } sum += min; v[k]=1; for(int j=1;j<=n;j++) if(!v[j] && dis[j]>map[k][j]) dis[j]=map[k][j]; } return sum; } int main() { int n,m; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if (i != j) map[i][j] = INF; else map[i][j] = 0; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&m); if (map[i][j] >= m) { map[i][j] = m; map[j][i] = m; } } printf("%lld\n",prim(n)); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。