P8074 [COCI2009-2010#7] SVEMIR 题解

· · 题解

前置知识：最小生成树。

给出 n 个点的三维坐标，可计算出所有点两两之间的距离。
这道题的难点在于存边。
如果 n 个点两两之间的所有边都存下来，那么一共要存 \frac{n \times (n-1)}{2} 条边。
而我们发现数据范围： n \leqslant 10^{5}
那么这样我们要存 5 \times 10^{9} 条边，显然会 MLE 。

考虑优化存边方法。
必须删边。
删边，就要删掉那些对于答案没有贡献的边，这些边可有可无。
我们来看一个例子： 

3
1 1 1
1 1 2
1 1 3

我们实际上并不需要连三条边，我们只用在第一个点和第二个点、第二个点和第三个点之间各连一条边就可以了。
得出思路：分别按照x、y、z从小到大排三次序，排完后再数组中相邻两项之间建边。
这样我们最多只用建 3 \times n 条边，当 n=10^{5} 时，边数也只会达到 300000。

显然这道题建立的是一个稀疏图，我们用 Kruskal 求解最小生成树。
代码奉上： 

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;//m为最后的边数
const int Maxn=1e5+5,Maxm=1e6+5;
struct Node//存点，num为点的编号
{
    int x,y,z,num;
}node[Maxn];
struct Edge//存边
{
    int u,v,w;
}graph[Maxm];
//前三个cmp是用在建边时的排序的，最后一个是用在kruskal中的排序的
bool cmpx(Node n1,Node n2) {return n1.x<n2.x;}
bool cmpy(Node n1,Node n2) {return n1.y<n2.y;}
bool cmpz(Node n1,Node n2) {return n1.z<n2.z;}
bool cmpw(Edge e1,Edge e2) {return e1.w<e2.w;}
int fa[Maxn];//并查集优化
int mst;
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y) {fa[find(x)]=find(y);}
void kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i;
    int count=0;
    sort(graph+1,graph+m+1,cmpw);
    for(int i=1;i<=m;i++)
    {
        Edge e=graph[i];
        int u=e.u,v=e.v,w=e.w;
        if(find(u)!=find(v)) 
        {
            merge(u,v);
            mst+=w;
            count++;
            if(count==n-1) return;
        }
    }
}
void add(int u,int v,int w)
{
    graph[++m].u=u;
    graph[m].v=v;
    graph[m].w=w;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].z);
        node[i].num=i; 
    }
    sort(node+1,node+n+1,cmpx);
    for(int i=1;i<n;i++) add(node[i].num,node[i+1].num,node[i+1].x-node[i].x);
    sort(node+1,node+n+1,cmpy);
    for(int i=1;i<n;i++) add(node[i].num,node[i+1].num,node[i+1].y-node[i].y);
    sort(node+1,node+n+1,cmpz);
    for(int i=1;i<n;i++) add(node[i].num,node[i+1].num,node[i+1].z-node[i].z);
    kruskal();
    cout<<mst;
    return 0;
}