POJ 1258 Agri-Net 最小生成樹
樸素的Prim!
#include <stdio.h>

int map[128][128], set[128], N, tm;

__inline int prim()


{
int sum, i, j, k, min_val, min_idx;

tm++;
set[0] = tm;
sum = 0;

for (i = 0; i < N - 1; i++)
{
min_val = 0x7fffffff;

for (j = 0; j < N; j++)
{
if (set[j] != tm)
continue;

for (k = 0; k < N; k++)
{

if (set[k] != tm && map[j][k] < min_val)
{
min_val = map[j][k];
min_idx = k;
}
}
}
sum += min_val;
set[min_idx] = tm;
}

return sum;
}

int main()


{
int i, j;

freopen("e:\\test\\in.txt", "r", stdin);


while (scanf("%d", &N) != EOF)
{
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
scanf("%d", &map[i][j]);
printf("%d\n", prim());
}

return 0;
}
#include <stdio.h>
int map[128][128], set[128], N, tm;
__inline int prim()

{
int sum, i, j, k, min_val, min_idx;
tm++;
set[0] = tm;
sum = 0;
for (i = 0; i < N - 1; i++)
{
min_val = 0x7fffffff;
for (j = 0; j < N; j++)
{
if (set[j] != tm)
continue;
for (k = 0; k < N; k++)
{
if (set[k] != tm && map[j][k] < min_val)
{
min_val = map[j][k];
min_idx = k;
}
}
}
sum += min_val;
set[min_idx] = tm;
}
return sum;
}
int main()

{
int i, j;
freopen("e:\\test\\in.txt", "r", stdin);

while (scanf("%d", &N) != EOF)
{
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
scanf("%d", &map[i][j]);
printf("%d\n", prim());
}
return 0;
}posted on 2010-03-14 00:42 糯米 閱讀(143) 評論(0) 編輯 收藏 引用 所屬分類: POJ
