lessons/参考实现/06-最小与最大生成树/AtCoder-arc076_b.cpp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <tuple>
#include <vector>
using namespace std;
struct DSU {
    vector<int> p, size;
    explicit DSU(int n) : p(n), size(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 (size[a] < size[b]) swap(a, b); p[b] = a; size[a] += size[b]; return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<long long> x(n), y(n); vector<int> order(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i], order[i] = i;
    vector<tuple<long long, int, int>> edges;
    auto add_neighbors = [&](const vector<long long> &coordinate) {
        sort(order.begin(), order.end(), [&](int a, int b) { return coordinate[a] < coordinate[b]; });
        for (int i = 1; i < n; ++i) {
            int u = order[i - 1], v = order[i];
            edges.push_back({min(abs(x[u] - x[v]), abs(y[u] - y[v])), u, v});
        }
    };
    add_neighbors(x); add_neighbors(y);
    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';
}