专栏文章

题解：P8074 [COCI 2009/2010 #7] SVEMIR

llailai0916qwq
P8074题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mino7rkh
此快照首次捕获于
2025/12/02 05:38
3 个月前
此快照最后确认于
2025/12/02 05:38
3 个月前
查看原文

题意简述

在三维空间中，给定 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) 的权值不大于该割的最小跨割边。
由最小生成树的 切割性质 可知，必存在一棵最小生成树完全由这些相邻边构成。

参考代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...