poj 1287

裸prim题。

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX 110
#define INF 0x3f3f3f3f

int n, count;
int map[MAX][MAX];
int visit[MAX];
int low[MAX];

int prim() {
  memset(visit, 0, sizeof(visit));
  int sum = 0;
  visit[1] = 1;
  for (int i = 1; i <= n; i++) {
    low[i] = map[i][1];
  }

  for (int i = 1; i < n; i++) {
    int minn = INF;
    int u;

    for (int j = 1; j <= n; j++) {
      if (!visit[j] && low[j] < minn) {
        minn = low[j];
        u = j;
      }
    }
    visit[u] = 1;
    sum += minn;
    for (int j = 1; j <= n; j++) {
      if (!visit[j] && low[j] > map[u][j]) {
        low[j] = map[u][j];
      }
    }
  }

  return sum;
}

int main(void) {
  while (~scanf("%d", &n)) {
    if (n == 0)
      break;
    scanf("%d", &count);
    memset(map, INF, sizeof(map));
    for (int i = 1; i <= count; i++) {
      int s, e, len;
      scanf("%d%d%d", &s, &e, &len);
      if (len < map[s][e]) {
        map[s][e] = len;
        map[e][s] = len;
      }
    }
    if (count == 0)
      printf("0\n");
    else
      printf("%d\n", prim());
  }

  return 0;
}