题解 | #还是畅通工程#

easy的题目当然要easy的解

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int find(map<int, int> mp, int x)
{
    if (mp[x] != x)
        mp[x] = find(mp, mp[x]);
    return mp[x];
}
int main()
{
    int n, w;
    map<int, int> mp;
    map<int, int> dist;
    vector<pair<int, pair<int, int> > > vec;
    while (cin >> n && n) {
        mp.clear();
        dist.clear();
        vec.clear();
        for (int i = 0; i < n; ++i) {
            mp[i + 1] = i + 1;
            dist[i + 1] = 0;
        }
        for (int i = 0, a, b; i < n * (n - 1) / 2; ++i) {
            cin >> a >> b >> w;
            vec.push_back(pair<int, pair<int, int> >(w, pair<int, int>(a, b)));
        }
        sort(vec.begin(), vec.end(), [](
            const pair<int, pair<int, int> > a, const pair<int, pair<int, int> > b) {
                return a.first < b.first;
            });
        for (int i = 0; i < n * (n - 1) / 2; ++i) {
            int ax = find(mp, vec[i].second.first);
            int bx = find(mp, vec[i].second.second);
            if (ax == bx)
                continue;
            else {
                mp[bx] = ax;
                dist[ax] += vec[i].first + dist[bx];
            }
        }
        cout << dist[find(mp, 1)] << endl;
    }
}