长乐 Day 5

今天学并查集和最小生成树
这有道让我很疑惑的题

序列破解
乍一看题目，觉得这跟生成树没什么关系
看完书后，发现是用什么前缀和来变成生成树
两个点分别为i-1和j，边权为输的x
那不简单吗，代码……e下面有

#include <bits/stdc++.h>
using namespace std;
const int L = 1e7 + 10;

int n, m, ans, k;
int f[3000];
struct Edge {
    int a, b, w;
} e[L];
int find(int x) {
    if (f[x] != x)
        f[x] = find(f[x]);
    return f[x];
}
bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; }
int main(void) {
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            int x;
            cin >> x;
            m++;
            e[m].a = i - 1, e[m].b = j, e[m].w = x;
        }
    sort(e + 1, e + 1 + m, cmp);
    for (int i = 0; i <= n; i++) f[i] = i;
    int k = 0;
    for (int i = 1; i <= m; i++) {
        int g = find(e[i].a), h = find(e[i].b);
        if (g != h) {
            f[g] = h;
            ans += e[i].w;
            k++;
            if (k == n)
                break;
        }
    }
    cout << ans;
    return 0;
}

没了（hbtm）