HOJ 1233 还是畅通工程（最小生成树，水题）

最小生成树，水题
本题要点：
1、套用 prim 模板即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 110, MaxM = 10010;
int fa[MaxN];
int n, m;
bool vis[MaxN];struct rec
{
    int x, y, z;bool operator<(const rec& rhs) const{
    return z < rhs.z;}
}edge[MaxM];int get(int x)
{
    if(fa[x] == x)return x;return fa[x] = get(fa[x]);
}int main()
{
    while(scanf("%d", &n) != EOF && n){
    for(int i = 1; i <= n; ++i)fa[i] = i;m = n * (n - 1) / 2;for(int i = 1; i <= m; ++i){
    scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);}int ans = 0;sort(edge + 1, edge + m + 1);for(int i = 1; i <= m; ++i){
    int x = get(edge[i].x), y = get(edge[i].y);if(x == y)	continue;fa[x] = y;ans += edge[i].z;}printf("%d\n", ans);}return 0;
}/* 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 *//* 3 5 */