C++ 解法, 执行用时: 156ms, 内存消耗: 9976KB, 提交时间: 2020-07-28

#include<stdio.h>
#include<algorithm>
using namespace std;
    
struct edge {
    int u, v, w;
    bool operator< (struct edge &A) const {
        return w < A.w;
    }
}E[200000];
    
int p[100002];
int val[100000];
    
int parents(int x) {
    if (x != p[x])
        p[x] = parents(p[x]);
    return p[x];
}
    
int main() {
    int t;
    scanf("%d", &t);
    while (t > 0) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d", &val[i]);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
        }
        for (int i = 0; i < n; i++) {
            E[i + m].u = n + 1;
            E[i + m].v = i + 1;
            E[i + m].w = val[i];
        }
        for (int i = 1; i <= n + 1; i++) {
            p[i] = i;
        }
        sort(E, E + n + m);
        long long sum = 0;
        for (int i = 0, cnt = 0; i < m + n && cnt <= n-1 ; i++) {
            int p_u = parents(E[i].u);
            int p_v = parents(E[i].v);
            if (p_v != p_u) {
                p[p_v] = p_u;
                sum += E[i].w;
                cnt++;
            }
        }
        printf("%lld\n", sum);
        t--;
    }
}

C++ 解法, 执行用时: 162ms, 内存消耗: 3508KB, 提交时间: 2020-10-29

#include<stdio.h>
#include<algorithm>
using namespace std;
   
struct edge {
    int u, v, w;
    bool operator< (struct edge &A) const {
        return w < A.w;
    }
}E[200000];
   
int p[100002];
int val[100000];
   
int parents(int x) {
    if (x != p[x])
        p[x] = parents(p[x]);
    return p[x];
}
   
int main() {
    int t;
    scanf("%d", &t);
    while (t > 0) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d", &val[i]);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
        }
        for (int i = 0; i < n; i++) {
            E[i + m].u = n + 1;
            E[i + m].v = i + 1;
            E[i + m].w = val[i];
        }
        for (int i = 1; i <= n + 1; i++) {
            p[i] = i;
        }
        sort(E, E + n + m);
        long long sum = 0;
        for (int i = 0, cnt = 0; i < m + n && cnt <= n-1 ; i++) {
            int p_u = parents(E[i].u);
            int p_v = parents(E[i].v);
            if (p_v != p_u) {
                p[p_v] = p_u;
                sum += E[i].w;
                cnt++;
            }
        }
        printf("%lld\n", sum);
        t--;
    }
}