题意简述

在三维空间中，给定 $n$ 个点 $(x_i,y_i,z_i)$，求这些点的最小生成树。

任意两点 $A$ 和 $B$ 之间的边权定义为：

$$\min\set{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|}$$

解题思路

思想

对所有点分别按 $x$、$y$、$z$ 三维坐标排序，每个排序中只连接相邻两点，共 $3(n-1)$ 条边。

利用 Kruskal 算法求最小生成树，时间复杂度为 $O(n\log n)$。

证明

设原完全图为 $G=(V,E)$，边权定义为：

$$w(u,v)=\min\set{|x_u-x_v|,|y_u-y_v|,|z_u-z_v|}$$

对任意割 $(S,V\setminus S)$，设 最小跨割边 为：

$$e^*=(u,v),w(e^*)=\min\set{|x_u-x_v|,|y_u-y_v|,|z_u-z_v|}$$

若该最小值由维度 $d\in\set{x,y,z}$ 取得，则：

$$w(e^*)=|d_u-d_v|$$

在所有点按 $d$ 排序的序列中，跨越割 $(S,V\setminus S)$ 的 相邻对 $(p,q)$ 必满足：

$$|d_p-d_q|=\min\set{|d_i-d_j|,i\in S,j\in V\setminus S}\le |d_u-d_v|=w(e^*)$$

由于 $w(p,q)\le |d_p-d_q|$，得：

$$w(p,q)\le w(e^*)$$

因此，对任意割存在一条候选边 $(p,q)$ 的权值不大于该割的最小跨割边。

由最小生成树的 切割性质 可知，必存在一棵最小生成树完全由这些相邻边构成。

参考代码

1.11 KBcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
struct Point
{
	int x,y,z;
}a[N];
struct Edge
{
	int u,v,w;
	bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
int fa[N],id[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
ll kruskal(int n)
{
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(E.begin(),E.end());
	ll ans=0,cnt=0;
	for(auto [u,v,w]:E)
	{
		if(cnt==n-1)break;
		int x=find(u),y=find(v);
		if(x==y)continue;
		fa[x]=y;
		ans+=w;
		cnt++;
	}
	return ans;
}
void add(int u,int v)
{
	int dx=abs(a[u].x-a[v].x),dy=abs(a[u].y-a[v].y),dz=abs(a[u].z-a[v].z);
	E.push_back({u,v,min({dx,dy,dz})});
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y>>a[i].z;id[i]=i;}
	sort(id+1,id+n+1,[](int u,int v){return a[u].x<a[v].x;});
	for(int i=1;i<n;i++)add(id[i],id[i+1]);
	sort(id+1,id+n+1,[](int u,int v){return a[u].y<a[v].y;});
	for(int i=1;i<n;i++)add(id[i],id[i+1]);
	sort(id+1,id+n+1,[](int u,int v){return a[u].z<a[v].z;});
	for(int i=1;i<n;i++)add(id[i],id[i+1]);
	cout<<kruskal(n)<<'\n';
	return 0;
}