还是畅通工程

典型的最小生成树问题
如何生成最小生成树 --> prim、Kruskal算法
选用Kruskal算法，如何判断两个顶点已经在同一集合？ --> 并查集
注意qsort对指针数组的应用

#include<stdio.h>
#include<stdlib.h>
typedef struct{
    int cost;
    int x;
    int y;
}Edge; // 边结构体
Edge *E[5100];
int father[101];
int cmp(const void *a,const void *b)
{
    Edge * x = *(Edge **)a;
    Edge * y = *(Edge **)b;
    return x->cost - y->cost;
}
void init()
{
    for(int i = 0;i<101;i++)
        father[i] = i;
    return;
}
int findfather(int i)
{
    if(father[i] == i)
        return i;
    else
        return findfather(father[i]);
}
int main()
{
    int N;
    while(scanf("%d",&N) != EOF && N)
    {
        int ans = 0;
        init(); // 初始化father数组
        for(int i = 0;i<N*(N-1) / 2; i++) // 读取边的信息
        {
            E[i] = (Edge *)malloc(sizeof(Edge));
            scanf("%d %d %d",&E[i]->x,&E[i]->y,&E[i]->cost);
        }
        qsort(E,N*(N-1) / 2,sizeof(Edge*),cmp); // 按边的权值升序排列
        int cnt = 0; // 计数目前最小生成树的边
        for(int i = 0;i<N*(N-1)/2;i++) // 利用Kruskal算法构造最小生成树
        {
            if(cnt == N-1) // 最小生成树已经构造好
                break;
            int fx = findfather(E[i]->x);
            int fy = findfather(E[i]->y);
            if(fx != fy) // 边的两端点不在同一集合中则合并
            {
                father[fx] = fy;
                ans += E[i]->cost;
                cnt++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}