POJ1287 Networking(最小生成树)

题意：

连通一个图，找最小权值和，有重边

要点：

因为有重边，所以Prim算法还要取最小的边加入，而Kruskal算法可以直接忽略这个问题，因为一开始要排序，大的自动舍掉了。这题很水，但我WA了快1个小时，原因init函数中，因为我是从0开始到n-1的，这题因为卡的比较紧，数据是从1~n的，所以这里少了一个数值一直WA，以后要注意这个地方。

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
using namespace std;
struct edge
{int u, v, len;
}e[5100];
int p[5100];
int n,m;bool cmp(edge a, edge b)
{return a.len < b.len;
}
void init()
{for (int i = 1; i <= n; ++i)//题目数据是从1~n的p[i] = i;
}
int find(int x)
{if (p[x] == x) return x;return p[x] = find(p[x]);
}
bool merge(int x, int y)
{x = find(x);y = find(y);if (x != y){p[y] = x;return true;}return false;
}
void kruskal()
{init();sort(e, e + m, cmp);int edges = 0,sum=0;for (int i = 0; i < m; ++i){if (merge(e[i].u, e[i].v)){sum += e[i].len;edges++;}if (edges + 1 == n)break;}printf("%d\n", sum);
}int main()
{while (scanf("%d", &n)==1&&n){scanf("%d", &m);for (int i = 0; i < m;++i){scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].len);}kruskal();}return 0;
}