题解 | #畅通工程#

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

const int maxnum=101;
int points[maxnum];
int height[maxnum];
struct path{
    int from;
    int to;
    int weight;
} paths[maxnum*(maxnum-1)/2];

bool compare(path p1,path p2){
    return p1.weight<p2.weight;
}

void init(int m){
    for(int i=0;i<m+1;++i){
        points[i]=i;
        height[i]=0;
    }
}

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

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

int kruskal(int n,int m){
    init(m);
    sort(paths,paths+n,compare);
    int weight=0;
    int x=0;
    for(int i=0;i<n;++i){
        path cur=paths[i];
        if(find(cur.to)==find(cur.from)) continue;
        else{
            x++;
            Union(cur.to, cur.from);
            weight+=cur.weight;
        }
    }
    if(x==m-1)
    return weight;
    return -1;
}

int main() {
    int n,m;
    while(cin>>n>>m){
        if(n==0) break;
        for(int i=0;i<n;++i){
            cin>>paths[i].from>>paths[i].to>>paths[i].weight;
        }
        int res=kruskal(n,m);
        if(res!=-1)
        cout<<res<<endl;
        else cout<<"?"<<endl;
    }
}