题解 | 还是畅通工程(kruskal)

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX=100;

struct edge{
    int from;
    int to;
    int length;
};

edge s[MAX*MAX];
int father[MAX];
int height[MAX];

void init(int n)
{
    for(int i=1; i<=n; i++)
    {
        father[i]=i;
        height[i]=0;
    }
}

int find(int x)
{
    if(father[x]!=x)
    {
        father[x]=find(father[x]);
    }
    return father[x];
}

void Union(int a, int b)
{
    a=find(a);
    b=find(b);
    if(a!=b)
    {
        if(height[a]>height[b])
        {
            father[b]=a;
        }
        else if(height[a]<height[b])
        {
            father[a]=b;
        }
        else{
            father[b]=a;
            height[a]++;
        }
    }
    return;
}

bool compare(edge a, edge b)
{
    return a.length<b.length;
}

int kruskal(int edgenum)
{
    int answer=0;
    sort(s,s+edgenum,compare);
    for(int i=0; i<edgenum; i++)
    {
        if(find(s[i].from)!=find(s[i].to))
        {
            Union(s[i].from,s[i].to);
            answer+=s[i].length;
        }
    }
    return answer;
}

int main() {
    int n;
    while (cin >> n) {
        if(n==0)
        {
            break;
        }
        int edgenum=n*(n-1)/2;
        init(n);
        for(int i=0; i<edgenum; i++)
        {
            cin >> s[i].from >> s[i].to >> s[i].length;
        }
        int answer=0;
        cout << kruskal(edgenum) << endl;
    }
    return 0;
}