TIOJ 1327：最小格子生成樹-EXTREME

TIOJ 1327：最小格子生成樹-EXTREME

題目大意：平面上有 $n$ 個點，想要用垂直或水平的線段把他們連起來，保證可以全部連起來，問所有線段最小長度總和。

解法：可以知道是最小生成樹的問題，只要 $x$ 座標相同或是 $y$ 座標相同的兩個點就連邊，但是一個一個找要 $O(n^2)$ 太慢了，其實可以先排序好再加入相鄰的就好了。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, m, x[SIZE], y[SIZE], esiz;
vector<int> lis;
vector<pair<int, int>> vx[2 * SIZE], vy[2 * SIZE];
tuple<int, int, int> e[2 * SIZE];

int to[SIZE], h[SIZE];

int dsu (int x) {
    return x == to[x] ? x : (to[x] = dsu (to[x]));
}

bool Merge (int a, int b) {
    a = dsu (a), b = dsu (b);
    if (a == b) {
        return 0;
    }
    if (h[a] < h[b]) {
        swap (a, b);
    }
    to[b] = a;
    h[a] += h[a] == h[b];
    return 1;
}

void solve() {
    cin >> n;
    lis = vector<int> (1, -1);
    fill (vx, vx + 2 * n + 1, vector<pair<int, int>>());
    fill (vy, vy + 2 * n + 1, vector<pair<int, int>>());
    FOR (i, 1, n) {
        cin >> x[i] >> y[i];
        lis.pb (x[i]);
        lis.pb (y[i]);
        h[i] = 0, to[i] = i;
    }
    sort (lis.begin(), lis.end());
    lis.erase (unique (lis.begin(), lis.end()), lis.end());
    m = lis.size() - 1;
    FOR (i, 1, n) {
        int pos = lower_bound (lis.begin(), lis.end(), x[i]) - lis.begin();
        vx[pos].pb (y[i], i);
        pos = lower_bound (lis.begin(), lis.end(), y[i]) - lis.begin();
        vy[pos].pb (x[i], i);
    }
    esiz = 0;
    FOR (i, 1, m) {
        sort (vx[i].begin(), vx[i].end());
        sort (vy[i].begin(), vy[i].end());
        FOR (j, 1, (int) vx[i].size() - 1) e[++esiz] = {vx[i][j].F - vx[i][j - 1].F, vx[i][j - 1].S, vx[i][j].S};
        FOR (j, 1, (int) vy[i].size() - 1) e[++esiz] = {vy[i][j].F - vy[i][j - 1].F, vy[i][j - 1].S, vy[i][j].S};
    }
    sort (e + 1, e + esiz + 1);
    long long ans = 0;
    FOR (i, 1, esiz) {
        auto [w, a, b] = e[i];
        ans += Merge (a, b) ? w : 0;
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！