题解 | #畅通工程#

#include<iostream>
#include<algorithm>
using namespace std;

struct node{
    int n1;
    int n2;
    int weight;
};
typedef struct node edge;

edge e[100];
int set[101];

int getfather(int i){
    if(set[i]==i) return i;
    return getfather(set[i]);
}

void merge_edge(int i,int& min){
    int x=getfather(e[i].n1);
    int y=getfather(e[i].n2);
    if(x!=y){
        if(x>y){
            set[x]=y;
        }else{
            set[y]=x;
        }
        min+=e[i].weight;
    }
}

bool cmp(edge l,edge r){//true no exchange
    return l.weight < r.weight;
}

int main(){
    int n,m;
    while(cin >> n >> m){
        if(n==0) break;
        for(int i=1;i<=m;i++){
            set[i]=i;
        }
        set[0]=-1;
        for(int i=0;i<n;i++){
            cin >> e[i].n1 >> e[i].n2 >> e[i].weight;
        }
        sort(e,&e[n],cmp);
        int min=0;
        for(int i=0;i<n;i++){
            merge_edge(i,min);
        }
        int tag=0;
        for(int i=1;i<=m;i++){
            if(set[i]==i){
                tag++;
            }
        }
        if(tag==1){
            cout << min << '\n';
        }else{
            cout << '?' << '\n';
        }
    }
    return 0;
}

套路题， 并查集加克鲁斯卡尔算法求最小生产树。