题解 | #畅通工程#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define len 1009
#define maxint 1<<31-1

int father[len];
int height[len];

void initial_it(){
    for(int i = 0;i<len;i++){
        father[i] = i;
        height[i] = 0;
    }
}

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

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

int set_num(int m){
    int res = 0;
    for(int i = 1;i<=m;i++){
        if(father[i]==i){
            res++;
        }
    }
    return res;
}

typedef struct node{
    int a;
    int b;
    int cost;
}line;

line initial_line(int a,int b,int cost){
    line l;
    l.a = a;
    l.b = b;
    l.cost = cost;
    return l;
}

int l,r;
line line_list[len];

void initial_list(){
    l = 0;
    r = 0;
}

void push_back(line l){
    line_list[r++] = l;
}

line pop_front(){
    return line_list[l++];
}

int cmp(const void*s1,const void*s2){
    line a1 = *(line*)s1;
    line a2 = *(line*)s2;
    return a1.cost-a2.cost;
}

void list_sort(){
    qsort(line_list+l,r-l,sizeof(line),cmp);
}

int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        if(n==0){
            break;
        }
        initial_it();
        initial_list();
        int a,b,cost;
        for(int i = 0;i<n;i++){
            scanf("%d %d %d",&a,&b,&cost);
            push_back(initial_line(a,b,cost));
        }
        int res = 0;
        while(l!=r&&set_num(m)!=1){
            list_sort(n);
            line l = pop_front();
            int a = find(l.a);
            int b = find(l.b);
            int cost = l.cost;
            if(a!=b){
                bind(a,b);
                res+=cost;
            }
        }
        if(set_num(m)!=1){
            printf("?\n");
        }
        else{
            printf("%d\n",res);
        }
    }
}