0829-T4 太空帝国
题意
给定一个图有 \(n\) 个点，每个点的坐标为 \((x_i,y_i,z_i)\)。
点 \(i\) 和点 \(j\) 的距离为 \(\min(|x_i-x_j|,|y_i-y_j|,|z_i-z_j|)\)。
求该图的最小生成树。
思路
暴力建图不能通过。
对最小生成树有贡献的边只可能连在按 \(x\) 或 \(y\) 或 \(z\) 排序后的相邻点之间。
以按 \(x\) 排序为例子证明。
排序后，对于 \(a < b < c\)，\(w(a,c)=w(a,b)+w(b,c)\)。
左右两边对于边权的贡献都一样，而右边多连了一个点，在最小生成树中更优。
证明 \(y,z\) 同理。
这样只有 \(O(n)\) 条边。
时间复杂度：\(O(n\log n)\)。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 5;
struct point {ll x, y, z, id;};
struct edge {ll x, y, z;};
struct DSU {
int fa[N];
void init(int n) {for (int i = 1; i <= n; i ++) fa[i] = i;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return ;
fa[fx] = fy;
}
bool same(int x, int y) {return find(x) == find(y);}
};
ll Abs(ll num) {return num > 0 ? num : -num;}
ll dis(point a, point b) {return min(Abs(a.x - b.x), min(Abs(a.y - b.y), Abs(a.z - b.z)));}
bool cmp(edge a, edge b) {return a.z < b.z;}
bool cmp1(point a, point b) {return a.x < b.x;}
bool cmp2(point a, point b) {return a.y < b.y;}
bool cmp3(point a, point b) {return a.z < b.z;}
int n; ll ans;
point p[N];
vector <edge> v;
DSU dsu;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> p[i].x >> p[i].y >> p[i].z, p[i].id = i;
sort(p + 1, p + n + 1, cmp1);
for (int i = 1; i < n; i ++)
v.push_back({p[i].id, p[i + 1].id, dis(p[i], p[i + 1])});
sort(p + 1, p + n + 1, cmp2);
for (int i = 1; i < n; i ++)
v.push_back({p[i].id, p[i + 1].id, dis(p[i], p[i + 1])});
sort(p + 1, p + n + 1, cmp3);
for (int i = 1; i < n; i ++)
v.push_back({p[i].id, p[i + 1].id, dis(p[i], p[i + 1])});
sort(v.begin(), v.end(), cmp);
dsu.init(n);
for (unsigned i = 0; i < v.size(); i ++) {
ll x = v[i].x, y = v[i].y, z = v[i].z;
if (dsu.same(x, y)) continue;
dsu.merge(x, y);
ans += z;
}
cout << ans << "\n";
return 0;
}