题解 | 畅通工程

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct road{
    int v1, v2, cost;
};

bool my_greater(const road &a, const road &b){
    return a.cost < b.cost;
};

int find_parent(const vector<int> &vec, const int &a){
    if(vec[a] == a) return a;
    else return find_parent(vec, vec[a]);
}

int connact(vector<int> &vec, const int &a, const int &b){
    int ap = find_parent(vec, a);
    int bp = find_parent(vec, b);
    if(ap != bp){
        vec[bp] = ap;
        return 1;
    } 
    else{
        return 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    while(cin >> N >> M){
        if(N == 0) break;
        vector<int> parent(M + 1, 0);
        for(int i = 1; i <= M; i++) parent[i] = i;
        vector<road> trans(N);
        int sum_road = 0;
        int sum_cost = 0;
        for(int i = 0; i < N; i++){
            cin >> trans[i].v1 >> trans[i].v2 >> trans[i].cost;
        }
        sort(trans.begin(), trans.end(), my_greater);
        for(int i = 0; i < N; i++){
            int x = connact(parent, trans[i].v1, trans[i].v2);
            if(x == 1){
                sum_road++;
                sum_cost += trans[i].cost;
            }
        }
        if(sum_road == M - 1) cout << sum_cost << "\n";
        else cout << "?" << "\n";
    }
    return 0;
}