CF1095F

题目传送门

#include <bits/stdc++.h>
#define int long long
#define DEBUG cout << "==============================" << endl
using namespace std;
const int MAXN = 1114514;
struct Edge {
    int w;
    int u, v;
} edge[MAXN * 2];

int parent[MAXN], a[MAXN];
int cnt = 0, u, v, w, cost = 0, used = 0, n, m;

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

// void test(int x, int y) {
//     int rx = find(x);
//     int ry = find(y);
//     if (rx != ry) {
//         parent[ry] = rx;
//     }
// }

void kruskal() {
    for (int i = 0; i < cnt - 1; i++) {
        for (int j = 0; j < cnt - i - 1; j++) {
            if (edge[j].w > edge[j + 1].w) {
                swap(edge[j], edge[j + 1]);
            }
        }
    }

    for (int i = 0; i < cnt; i++) {
        if (used == n - 1)
            break;
        Edge e = edge[i];
        if (find(e.u) != find(e.v)) {
            cost += e.w;
            // cout << cost << endl;
            // DEBUG;
            int rx = find(e.u);
            int ry = find(e.v);
            if (rx != ry) {
                parent[ry] = rx;
                // cout << "ry:" << ry << " rx:" << rx << endl;
            }
            used++;
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        parent[i] = i;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            edge[cnt++] = {a[i] + a[j], i, j};
        }
    }
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        edge[cnt++] = {w, u, v};
    }
    kruskal();
    cout << cost;
    return 0;
}

RE#8 不知道爆哪了