畅通工程

最小生成树，kruskal，并查集

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct Node{
    int s; // 起点
    int d; // 终点
    int dis; // 距离
}Edge;
Edge E[100];
int father[101];
int N,M;
void init()
{
    for(int i = 0;i<=M;i++)
        father[i] = i;
}
int findfather(int n)
{
    if(father[n] == n)
        return n;
    else
        return findfather(father[n]);
}

int cmp(const void*a,const void*b)
{
    Edge *x = (Edge *)a;
    Edge *y = (Edge *)b;
    return x->dis - y->dis;
}
int kruskal()
{
    int ans = 0;
    qsort(E,N,sizeof(Edge),cmp);
    int j = 0;
    for(int i = 0;i<N;i++)
    {
        if(j == M-1)
            break;
        int x,y;
        //合并
        x = findfather(E[i].s);
        y = findfather(E[i].d);
        if(x!=y)
        {
            father[x] = y;
            ans += E[i].dis;
            j++;
        }
        else
            continue;
    }
    if(j == M-1)
        return ans;
    else
        return 0;
}

int main()
{
    while(scanf("%d",&N)!=EOF && N)
    {
        scanf("%d", &M);
        init(); // father初始化
        for (int i = 0; i < N; i++)
            scanf("%d%d%d", &E[i].s, &E[i].d, &E[i].dis);
        int ans = kruskal();
        if (ans)
            printf("%d\n", ans);
        else
            printf("?\n");
    }
    return 0;
}