|
|
樸素的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;
}
|