题解 | #畅通工程#

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

const int N=100;
int father[N];
int height[N];

struct edge{
    int from;
    int to;
    int cost;
}edges[1000];

void initial(int n){
    for(int i=1;i<=n;i++){
        father[i]=i;
        height[i]=0;
    }
}

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

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

bool comp(edge a,edge b){
    return a.cost<b.cost;
}

int Kruscal(int n,int num){//n个点num条边
    initial(n);//对节点初始化
    int sum=0;
    sort(edges+1,edges+num+1,comp);
    for(int i=1;i<=num;i++){
        edge current = edges[i];
        if(find(current.from)!=find(current.to)) 
        {
            Union(current.from, current.to);
            sum+=current.cost;
        }
    }
    return sum;
}

int main() {
    int n,m;
    while(cin>>n>>m){//n条边m个村
        if(n==0) break;
        for(int i=1;i<=n;i++){
            cin>>edges[i].from>>edges[i].to>>edges[i].cost;
        }
        int answer=Kruscal(m,n);
        int a=0;//计算是否单连通
        for(int i=1;i<=n;i++){
            if(find(i)==i) a++;
        }
        if(a==1&&n>=m-1)
            cout<<answer<<endl;
        else
            cout<<'?'<<endl;
    }
}
// 64 位输出请用 printf("%lld")