POJ1258 Agri-Net【最小生成树】

 

POJ1258 Agri-Net【最小生成树】
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; }
POJ1258 Agri-Net【最小生成树】

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/04/15/2450739.html,如需转载请自行联系原作者

上一篇:Zabbix5之二:Zabbix监控项配置详解


下一篇:工作中的积累