题解 | #还是畅通工程#

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

struct Point
{
    double x;
    double y;
};

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

const int MAXN = 101;
struct Edge edge[MAXN * MAXN];
struct Point point[MAXN];
int father[MAXN];
int height[MAXN];
// 定义比较函数，用于排序
int compare(const void *a, const void *b) {
    // 将void指针转换为Edge结构体指针
    const struct Edge *edgeA = (const struct Edge *)a;
    const struct Edge *edgeB = (const struct Edge *)b;

    // 根据边的长度进行比较
    if (edgeA->length < edgeB->length)
        return -1;
    else if (edgeA->length > edgeB->length)
        return 1;
    else
        return 0;
}
void InitialF(int n)
{
    for (int i = 0; i < n; i++)
    {
        father[i] = i;
        height[i] = 0;
    }
}



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

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if (x != y)
    {
        if (height[x] > height[y])
            father[y] = x;
        else if (height[y] > height[x])
            father[x] = y;
        else
        {
            father[y] = x;
            height[x]++;
        }
    }
    return;
}

int KrusKal(struct Edge edge[], int father[], int height[], int n, int edgeNumber)
{
    InitialF(n);
    int s =0;
    qsort(edge, edgeNumber, sizeof(struct Edge), compare);
    double answer = 0;
    for (int i = 0; i < edgeNumber; i++)
    {
        if (Find(edge[i].from) != Find(edge[i].to))
        {
            Union(edge[i].from, edge[i].to);
            s+=edge[i].length;
            answer += sqrt(edge[i].length);
        }
    }
    return s;
}

int main()
{
    int n, a, b, c;
    while (scanf("%d", &n) == 1)
    {
        if (n <= 0) break;
        int edgeNumber = n * (n - 1) / 2;
        for (int i = 0; i < n*(n-1)/2; i++)
            scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].length);
       
        //Initial(n);
        printf("%d\n", KrusKal(edge, father, height, n, edgeNumber));
    }
    return 0;
}