五个推进网站建设工作,品牌建设最高境界是培育客户成为,做网站域名解析,135编辑器 wordpress[COCI2009-2010#7] SVEMIR
题目描述
太空帝国要通过建造隧道来联通它的 NNN 个星球。
每个星球用三维坐标 (xi,yi,zi)(x_i,y_i,z_i)(xi,yi,zi) 来表示#xff0c;而在两个星球 A,BA,BA,B 之间建造隧道的价格为 min{∣xA−xB∣,∣yA−yB∣,∣zA−zB∣}\min\{|x_A-x_…[COCI2009-2010#7] SVEMIR
题目描述
太空帝国要通过建造隧道来联通它的 NNN 个星球。
每个星球用三维坐标 (xi,yi,zi)(x_i,y_i,z_i)(xi,yi,zi) 来表示而在两个星球 A,BA,BA,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−1N-1N−1 条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。
输入格式
第一行一个整数 NNN。
接下来的 NNN 行每行三个整数 xi,yi,zix_i,y_i,z_ixi,yi,zi表示第 iii 个星球的坐标。
数据保证不存在两个具有相同坐标的星球。
输出格式
输出所需的最小总价。
样例 #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≤1051 \le N \le 10^51≤N≤105−109≤xi,yi,zi≤109-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 原题设置满分 100100100。
最小生成树如果把每两个点之间的边都存储会超时超空间。 放宽条件问题等价于每个点之间有三条边边权分别是|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 maxn1e50.5;
int m,n;
ll ans;
int pre[maxn5];
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 we.w;}};
vectorEdgeedges;struct Node
{int x,y,z,idx;bool operator (const Node b) const{return xb.x;}
} nodes[maxn5];bool cmp_y(Node a, Node b) {return a.yb.y;}
bool cmp_z(Node a, Node b) {return a.zb.z;}void init()
{m0;edges.clear();ans0;for0(i,n1) pre[i]i;
}int findroot(int x) {return pre[x]x?x: pre[x] findroot(pre[x]);}
bool merge(int x,int y)
{int rootxfindroot(x);int rootyfindroot(y);if (rootxrooty) return false;pre[rootx]rooty;return true;
}int main()
{std::ios::sync_with_stdio(false);while(cinn){for1(i,n){cinnodes[i].xnodes[i].ynodes[i].z;nodes[i].idxi;}init();sort(nodes1,nodesn1);// for1(i,n)
// {
// coutnodes[i].x nodes[i].y nodes[i].z;
// }for1(i,n-1){int disabs(nodes[i].x-nodes[i1].x);edges.push_back( Edge(nodes[i].idx,nodes[i1].idx,dis));}sort(nodes1,nodesn1,cmp_y);for1(i,n-1){int disabs(nodes[i].y-nodes[i1].y);edges.push_back( Edge(nodes[i].idx,nodes[i1].idx,dis));}sort(nodes1,nodesn1,cmp_z);for1(i,n-1){int disabs(nodes[i].z-nodes[i1].z);edges.push_back( Edge(nodes[i].idx,nodes[i1].idx,dis));}sort(edges.begin(),edges.end());medges.size();// for0(i,m)
// {
// coutedges[i].u edges[i].v edges[i].wendl;
// }int Tn-1;for0(i,m){Edge e edges[i];int ue.u,ve.v,we.w;if(!merge(u,v)) continue;ans w;if (--T0) 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
*/
