Skip to main content

P8074 [COCI 2009/2010 #7] SVEMIR

· 3 min read
lailai
lailai
Student & Developer

题意简述​

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

任意两点 AA 和 BB 之间的边权定义为：

min⁡{ ∣xA−xB∣,∣yA−yB∣,∣zA−zB∣ }\min\set{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|}

解题思路​

思想​

对所有点分别按 xx、yy、zz 三维坐标排序，每个排序中只连接相邻两点，共 3(n−1)3(n−1) 条边。

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

证明​

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

w(u,v)=min⁡{ ∣xu−xv∣,∣yu−yv∣,∣zu−zv∣ }w(u,v)=\min\set{|x_u-x_v|,|y_u-y_v|,|z_u-z_v|}

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

e∗=(u,v),w(e∗)=min⁡{ ∣xu−xv∣,∣yu−yv∣,∣zu−zv∣ }e^*=(u,v),w(e^*)=\min\set{|x_u-x_v|,|y_u-y_v|,|z_u-z_v|}

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

w(e∗)=∣du−dv∣w(e^*)=|d_u-d_v|

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

∣dp−dq∣=min⁡{ ∣di−dj∣,i∈S,j∈V∖S }≤∣du−dv∣=w(e∗)|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)≤∣dp−dq∣w(p,q)\le |d_p-d_q|，得：

w(p,q)≤w(e∗)w(p,q)\le w(e^*)

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

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

参考代码​

#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,min(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;
}