题解 | 还是畅通工程

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

struct Point{
    int x;
    int y;
};
struct Edge{
    int from;
    int to;
    int length;
};

struct Point point[100];
struct Edge edge[100*99/2];
int father[100];
int heigth[100];
void initial(int n){
    int i;
    for (i = 0; i < n; i++){
        father[i] = i;
        heigth[i] = 0;
    }
        
}

int Find(int i){

        if (i != father[i]){
            father[i] = Find(father[i]);
        }
    
    return father[i];
}

void Uion(int a, int b){
    a = Find(a);
    b = Find(b);
    if (a != b){
        if (heigth[a] < heigth[b]){
            father[a] = b;
        }
        else if (heigth[a] > heigth[b])
        {
            father[b] = a;
        }
        else{
            father[b] =a;
            heigth[a]++;
        }
        
    }
}

int cmp(const void *a, const void *b){
    const struct Edge*edga = (const struct Edge*)a;
    const struct Edge*edgb = (const struct Edge*)b;
    if(edga->length < edgb->length) return -1;
    if (edga->length > edgb->length) return 1;
    return 0;
    
}
int kruskal(int n, int edgenum){
    initial(n);
    int ans = 0;
    qsort(edge, edgenum, sizeof(struct Edge), cmp);
    for (int i = 0; i < edgenum; i++){
        if (Find(edge[i].from) != Find(edge[i].to)){
            Uion(edge[i].from, edge[i].to);
                ans += edge[i].length;
        }
    }
    return ans;

}



int main(){
    int n, res;
    int a[100];
    while(scanf("%d", &n) != EOF){
        if (n == 0) break;
        for(int i = 0; i < n*(n-1)/2; i++){
            scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].length);
        }
        res = kruskal(n, n*(n-1)/2);
        printf("%d\n", res);
    }
    return 0;
}