P8074 [COCI2009-2010#7] SVEMIR题解

· · 题解

P8074 [COCI2009-2010#7] SVEMIR题解

题目传送门

1. 题目大意

在一个三维坐标系中，给你 n 个点，建造一个连接 i、j 的边的代价是 \min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\}，在使得整个图连通时代价最小。

2. 分析

如果打一遍 Prim，时间复杂度为 O(n^2),1 \le N \le 10^5，无法 AC。

我们考虑 Kruskal：如果每个点两两建一条边，空间会炸，要优化空间。

我们看一下样例 #2:

3
-1 -1 -1 //一号
5 5 5    //二号
10 10 10 //三号

如果两两建边，会计算大量的无效数据，就像一号和三号点，我们只需要连接一号和二号，那为什么要连一号和三号呢？不难得出，当 x_a \le x_b \le x_c 时，只需连接 a，b 和 b，c，不需要关心 a，c。y，z 也是这样，这样只需建 3n 条边。也就是说，我们按 x，y，z 从小到大排序再建一条连接相邻两个点的边，最后在跑一遍 Kruskal。

3. Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5, MAXM = 1e7;

int n, m, ans, k;
int f[MAXN];
struct Edge {int u, v, w;}edge[MAXM];
bool operator < (const Edge &a, const Edge &b) {return a.w < b.w;}
struct Planet
{
    int x, y, z, id;
    void input (int i) {scanf ("%d%d%d", &x, &y, &z);id = i;}
}planet[MAXN];
bool cmpx (Planet a, Planet b) {return a.x < b.x;}
bool cmpy (Planet a, Planet b) {return a.y < b.y;}
bool cmpz (Planet a, Planet b) {return a.z < b.z;}

void init ()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)    planet[i].input (i);
    for (int i = 1; i <= n; i++)    f[i] = i;
}

// 并查集 
int find (int x)
{
    if (x != f[x])  f[x] = find (f[x]);
    return f[x];
}

void add (Planet a, Planet b)
{
    edge[++m].u = a.id;edge[m].v = b.id;
    edge[m].w = min (abs (a.x - b.x), min (abs (a.y - b.y), abs (a.z - b.z))); // 计算代价 
}

// 最小生成树 
void Kruska ()
{
    sort (edge + 1, edge + m + 1);
    for (int i = 1; i <= m; i++)
    {
        int r1 = find (edge[i].u), r2 = find (edge[i].v);
        if (r1 == r2)   continue;
        f[r2] = r1;
        k++;ans += edge[i].w;
        if (k == n - 1) return;// 建好了树就退出 
    }
}

int main()
{
    init ();
    // 排序 + 建一条连接相邻两个点的边
    sort (planet + 1, planet + n + 1, cmpx);
    for (int i = 2; i <= n; i++)    add (planet[i - 1], planet[i]);
    sort (planet + 1, planet + n + 1, cmpy);
    for (int i = 2; i <= n; i++)    add (planet[i - 1], planet[i]);
    sort (planet + 1, planet + n + 1, cmpz);
    for (int i = 2; i <= n; i++)    add (planet[i - 1], planet[i]);
    Kruska ();
    printf ("%d", ans);
    return 0;
}