P8074 [COCI2009-2010#7] SVEMIR 最小生成树

[COCI2009-2010#7] SVEMIR

题目描述

太空帝国要通过建造隧道来联通它的 $N$ 个星球。

每个星球用三维坐标 $(x_i,y_i,z_i)$ 来表示，而在两个星球 $A,B$ 之间建造隧道的价格为 min⁡{∣xA−xB∣,∣yA−yB∣,∣zA−zB∣}\min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\}min{∣xA​−xB​∣,∣yA​−yB​∣,∣zA​−zB​∣}。

现要建造 $N-1$ 条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。

输入格式

第一行，一个整数 $N$。

接下来的 $N$ 行，每行三个整数 $x_i,y_i,z_i$，表示第 $i$ 个星球的坐标。

数据保证不存在两个具有相同坐标的星球。

输出格式

输出所需的最小总价。

样例 #1

样例输入 #1

2
1 5 10
7 8 2

样例输出 #1

3

样例 #2

样例输入 #2

3
-1 -1 -1
5 5 5
10 10 10

样例输出 #2

11

样例 #3

样例输入 #3

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

样例输出 #3

4

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，$1\le N\le 10^5$，$-10^9\le x_i,y_i,z_i\le 10^9$。

【提示与说明】

题目译自 COCI 2009-2010 CONTEST #7 Task 4 SVEMIR。

本题分值按 COCI 原题设置，满分 $100$。

最小生成树，如果把每两个点之间的边都存储，会超时超空间。
放宽条件，问题等价于每个点之间有三条边，边权分别是|x1-x2|，|y1-y2|，|z1-z2|，然后求最小生成树距离。
所以观察规律，如果按x排序，只用在相邻次序的点之间建立x插值边，分析得知相隔的点对pi,pk (|i-k|!=1)建立的x差值边一定用不上(如果这两点在两棵树上，想要连通这两棵树，选择x差值边，一
定不如它们中间一点到其中某一点的x差值边来得好)。
按照y和z排序同理。

#include <bits/stdc++.h>
#define for0(a,n) for(int (a)=0;(a)<(n);(a)++)
#define for1(a,n) for(int (a)=1;(a)<=(n);(a)++)
typedef  long long ll;using namespace std;const int maxn=1e5+0.5;
int m,n;
ll ans;
int pre[maxn+5];
struct Edge
{int u,v,w;Edge(){}Edge(int u,int v,int w):u(u),v(v),w(w){}bool operator<(const Edge & e) const{return w<e.w;}};
vector<Edge>edges;struct Node
{int x,y,z,idx;bool operator <(const Node & b) const{return x<b.x;}
} nodes[maxn+5];bool cmp_y(Node & a, Node & b) {return a.y<b.y;}
bool cmp_z(Node & a, Node & b) {return a.z<b.z;}void init()
{m=0;edges.clear();ans=0;for0(i,n+1) pre[i]=i;
}int findroot(int x) {return pre[x]==x?x: pre[x]= findroot(pre[x]);}
bool merge(int &x,int &y)
{int rootx=findroot(x);int rooty=findroot(y);if (rootx==rooty) return false;pre[rootx]=rooty;return true;
}int main()
{std::ios::sync_with_stdio(false);while(cin>>n){for1(i,n){cin>>nodes[i].x>>nodes[i].y>>nodes[i].z;nodes[i].idx=i;}init();sort(nodes+1,nodes+n+1);//        for1(i,n)
//        {
//            cout<<nodes[i].x<<" "<<nodes[i].y<<" "<<nodes[i].z;
//        }for1(i,n-1){int dis=abs(nodes[i].x-nodes[i+1].x);edges.push_back( Edge(nodes[i].idx,nodes[i+1].idx,dis));}sort(nodes+1,nodes+n+1,cmp_y);for1(i,n-1){int dis=abs(nodes[i].y-nodes[i+1].y);edges.push_back( Edge(nodes[i].idx,nodes[i+1].idx,dis));}sort(nodes+1,nodes+n+1,cmp_z);for1(i,n-1){int dis=abs(nodes[i].z-nodes[i+1].z);edges.push_back( Edge(nodes[i].idx,nodes[i+1].idx,dis));}sort(edges.begin(),edges.end());m=edges.size();//        for0(i,m)
//        {
//            cout<<edges[i].u<<" "<<edges[i].v<<" "<<edges[i].w<<endl;
//        }int T=n-1;for0(i,m){Edge & e = edges[i];int u=e.u,v=e.v,w=e.w;if(!merge(u,v)) continue;ans+= w;if (--T==0) break;}printf("%lld\n",ans);}return 0;
}
/*
2
1 5 10
7 8 23
-1 -1 -1
5 5 5
10 10 105
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
*/