题解 | #畅通工程#最小生成树Kruskal

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int S[101];
struct Edge{
    int a,b;
    int cost;
}edge[10001];
bool cmp(Edge e1,Edge e2){
    return e1.cost<e2.cost;
}//排序的比较函数
void Initial(int n){
    int i;
    for(i=1;i<=n;i++)S[i]=-1;
}//对父节点的初始化
int find(int x){
    while(S[x]>=0)x=S[x];
    return x;
}//找到父节点
void Union(int root1,int root2){
    if(root1==root2)return;
    S[root1]=root2;
}//加入并查集
int main() {
    int n,m,i,price,res;
    while (cin >> n>>m&&n!=0) { // 注意 while 处理多个 case
        Initial(m);
        price=0;res=0;
        for(i=0;i<n;i++){
            cin>>edge[i].a>>edge[i].b>>edge[i].cost;
        }
        sort(edge,edge+n,cmp);//按照代价从小到大对道路进行排序
        for(i=0;i<n;i++){
            if(find(edge[i].a)!=find(edge[i].b)){
                price+=edge[i].cost;
                Union(find(edge[i].a),find(edge[i].b));//当选定该节点为边时加入并查集
            }
        }
        for(i=1;i<=m;i++){
            if(S[i]==-1)res++;//判断连通图数目
        }
        if(res!=1)cout<<'?';//如果有一个以上连通图说明不能实现畅通
        else cout<<price;
        cout<<endl;
    }
}
// 64 位输出请用 printf("%lld")