P8074 [COCI2009-2010#7] SVEMIR 题解

· · 题解

P8074 [COCI2009-2010#7] SVEMIR 题解

题意

给出 n 个点的坐标，问将所有点连通所需的最小花费。

朴素做法

首先，看到连通和最小花费，想到这题要求图的最小生成树，用并查集实现 kruskal 算法，以此得出这个图的最小生成树。

kruskal 算法流程：

  1. 建立并查集，每个点自己为一个集合

  2. 输入边并按照权值由小到大排序

  3. 扫描每一条边，如果两端点在同一集合则忽略，否则合并他们的集合，将这条边的权值累加进答案

很明显，这种做法的空间复杂度无法达到题目 32 MB 的要求，原因在于此题的图为完全图，任意两点之间都有边连接。

优化

再仔细看看题目，而从权值的计算公式中我们可以得到思路，将三个坐标分别存于不同数组并排序，计算相邻两点边权然后存边排序，这样也能保证边最小且点连通，代码如下。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll len=0;
struct planet{
    ll val,num;
}x[100001],y[100001],z[100001];
struct road{
    ll l,r,val;
}roa[1000001];
ll edge(ll a,ll b){//存边。
    ll tmpx=abs(x[a].val-x[b].val);
    ll tmpy=abs(y[a].val-y[b].val);
    ll tmpz=abs(z[a].val-z[b].val);
    roa[++len]=((road){x[a].num,x[b].num,tmpx});
    roa[++len]=((road){y[a].num,y[b].num,tmpy});
    roa[++len]=((road){z[a].num,z[b].num,tmpz});
}
ll k[100001];
ll find(ll x){
    if(x==k[x]) return k[x]=x;
    else return k[x]=find(k[x]);
}
bool cmp(planet a,planet b){
    return a.val<b.val;
}
bool cmp2(road a,road b){
    return a.val<b.val;
}
int main(){
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>x[i].val>>y[i].val>>z[i].val;
        x[i].num=i;y[i].num=i;z[i].num=i;//记录编号，存边用。
        k[i]=i;
    }
    sort(x+1,x+n+1,cmp);
    sort(y+1,y+n+1,cmp);
    sort(z+1,z+n+1,cmp);
    ll tot=0,ans=0;
    for(ll i=2;i<=n;i++){
        edge(i-1,i);//一个循环搞定，效率高还省空间。
    }
    sort(roa+1,roa+len+1,cmp2);
    for(ll i=1;i<=len;i++){
        ll x=roa[i].l,y=roa[i].r;
        ll tmpx=find(x),tmpy=find(y);
        if(tmpx!=tmpy){
            tot++;
            k[tmpx]=tmpy;
            ans+=roa[i].val;
        }
        if(tot==n-1) break;
    }//kruskal
    cout<<ans;
}