POJ 1287 Networking（最小生成树，prim ，裸题）

题目意思：
给出n个点（点号1 ~ n）, m条边双向边，边的数量不定，每两个点可能有多条边，题目 要求最小生成树的所有边之和；

本题要点：
1、 n == 50 ,很小，用邻接矩阵来存。显然存的是最短边。边稠密，用prim算法来算最小生成树.
2、 题目可能出现莫名其妙的 runtime error 的问题， 邻接矩阵 a[i][i] 初始化为0就会出现这种情况。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 60;
int a[MaxN][MaxN], d[MaxN], n, m, ans;
bool vis[MaxN];void prim()
{
    memset(d, 0x3f, sizeof(d));memset(vis, false, sizeof(vis));d[1] = 0;for(int i = 1; i < n; ++i)	//循环 n - 1 次{
    int x = 0;for(int j = 1; j <= n; ++j){
    if(!vis[j] && (0 == x || d[j] < d[x])){
    x = j;}}vis[x] = true;for(int y = 1; y <= n; ++y){
    if(!vis[y]){
    d[y] = min(d[y], a[x][y]);}}}
}int main()
{
    while(scanf("%d", &n) != EOF && n){
    scanf("%d", &m);memset(a, 0x3f, sizeof(a));// for(int i = 1; i <= m; ++i)// {
    // a[i][i] = 0; //这个不要写，写了就 runtime error // }for(int i = 1; i <= m; ++i){
    int x, y, z;scanf("%d%d%d", &x, &y, &z);a[x][y] = a[y][x] = min(z, a[x][y]);}prim();ans = 0;for(int i = 2; i <= n; ++i){
    ans += d[i];}printf("%d\n", ans);}return 0;
}/* 1 02 3 1 2 37 2 1 17 1 2 683 7 1 2 19 2 3 11 3 1 7 1 3 5 2 3 89 3 1 91 1 2 325 7 1 2 5 2 3 7 2 4 8 4 5 11 3 5 10 1 5 6 4 2 120*//* 0 17 16 26 */