[COCI2009-2010#7] SVEMIR
题目描述
太空帝国要通过建造隧道来联通它的 N N N 个星球。
每个星球用三维坐标 ( x i , y i , z i ) (x_i,y_i,z_i) (xi,yi,zi) 来表示,而在两个星球 A , B A,B A,B 之间建造隧道的价格为 min { ∣ x A − x B ∣ , ∣ y A − y B ∣ , ∣ z A − z B ∣ } \min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\} min{∣xA−xB∣,∣yA−yB∣,∣zA−zB∣}。
现要建造 N − 1 N-1 N−1 条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。
输入格式
第一行,一个整数 N N N。
接下来的 N N N 行,每行三个整数 x i , y i , z i x_i,y_i,z_i xi,yi,zi,表示第 i 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 % 100\% 100% 的数据, 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1≤N≤105, − 1 0 9 ≤ x i , y i , z i ≤ 1 0 9 -10^9 \le x_i,y_i,z_i \le 10^9 −109≤xi,yi,zi≤109。
【提示与说明】
题目译自 COCI 2009-2010 CONTEST #7 Task 4 SVEMIR。
本题分值按 COCI 原题设置,满分 100 100 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 2
3
-1 -1 -1
5 5 5
10 10 10
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
*/