lessons/参考实现/06-最小与最大生成树/CodeForces-1095F.cpp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <tuple>
#include <vector>
using namespace std;
struct DSU {
    vector<int> p, s;
    explicit DSU(int n) : p(n), s(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return false;
        if (s[a] < s[b]) swap(a, b); p[b] = a; s[a] += s[b]; return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    vector<tuple<long long, int, int>> edges;
    edges.reserve(m + n - 1);
    while (m--) {
        int u, v; long long w; cin >> u >> v >> w;
        edges.push_back({w, u - 1, v - 1});
    }
    int hub = int(min_element(a.begin(), a.end()) - a.begin());
    for (int v = 0; v < n; ++v) if (v != hub) edges.push_back({a[hub] + a[v], hub, v});
    sort(edges.begin(), edges.end());
    DSU dsu(n); long long answer = 0;
    for (auto [w, u, v] : edges) if (dsu.unite(u, v)) answer += w;
    cout << answer << '\n';
}