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}$,歡迎追蹤!
留言
張貼留言