POJ 1258 Agri-Net
浏览数：70 /
时间：2015年06月09日
/*
*POJ 1258 Agri-Net
*求最小生成树权值和
*/
#include <cstdio>
#include <cstring>
#define INF 1000000
#define MAXN 101
int mark, n;
int map[MAXN][MAXN];
int lowcost[MAXN];
int prime()
{
int i, j;
int sum = 0;
mark = 0;
lowcost[0] = -1;
for (i = 1; i < n; i++) {
lowcost[i] = map[0][i];
}
for (i = 1; i < n ; i++) {
int min = INF;
for (j = 0; j < n; j++) {
if (lowcost[j] != -1 && lowcost[j] < min) {
min = lowcost[j];
mark = j;
}
}
sum += min;
lowcost[mark] = -1;
for (j = 0; j < n; j++) {
if (map[mark][j] < lowcost[j]) {
lowcost[j] = map[mark][j];
}
}
}
return sum;
}
int main()
{
int i, j;
while (~scanf("%d", &n)) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &map[i][j]);
}
}
printf("%d\n", prime());
}
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
