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

· · 题解

题意简述

在三维空间中，给定 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) 的权值不大于该割的最小跨割边。

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

参考代码

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