最小生成树
时间限制: 1 Sec 内存限制: 64 MB
提交: 11 解决: 2
[提交][状态][讨论版]
题目描述
某个宇宙帝国有N个星球，由于宇宙的空间是三维的，因此每个星球的位置可以用三维坐标(X，Y，Z)来表示。任意两个不同的星球i和j都有一条边相连，边的距离是这样计算的：dis[i，j]=min(|Xi-Xj|，|Yi-Yj|，|Zi-Zj|)，其中| | 符号表示取绝对值。现在让你来挑N-1条边，让这N个星球连通成一个最小生成树，输出构成最小生成树的N-1条边的长度总和。
输入
第1行，一个整数N(1≤N≤100000)。
接下来有N行，每行三个整数X，Y，Z，表示一个星球的坐标，-1000000000≤X，Y，Z≤1000000000。没有两个星球的位置完全重叠。
输出
1行，构成最小生成树的N-1条边的长度总和。
样例输入
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
样例输出
4
【分析】又一道最小生成树，还是Kruskal算法，本以为能很快写出来，但一开始的建边就把我难住了，注意N≤100000，如果用二重循环建边指定超时。
所以我们可以将x,y,z分别排序，然后用结构体放进优先队列，再Kruskal就行了。下面是AC代码。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include<functional>
#define mod 1000000007
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int N=100005;
int n,m,k,cnt=-1;
int d[4][2]= {0,1,1,0,0,-1,-1,0};
int parent[N+60];
bool vis[N];
struct man {
int u,v,w;
bool operator<(const man&a)const{
return w>a.w;//最小值优先
}
} edg[N];//结构体存节点与节点之间的权值,x,y,z各存一份
priority_queue<man>q;//优先队列
struct mann
{
int x,y,z,id;
}mp[N];
bool cmp1(mann g,mann h) {return g.x<h.x;}
bool cmp2(mann g,mann h) {return g.y<h.y;}
bool cmp3(mann g,mann h) {return g.z<h.z;}//分别对x,y,z从小到大排序
void init() {
for(int i=0; i<=n; i++)parent[i]=i;
}//初始化
int Find(int x) {
if(parent[x] != x) parent[x] = Find(parent[x]);
return parent[x];
}//查找并返回节点x所属集合的根节点
void Union(int x,int y) {
x = Find(x);
y = Find(y);
if(x == y) return;
parent[y] = x;
}//将两个不同集合的元素进行合并
void Build()//将空间图转化为树，分别将两点间的x,y,z方向上的距离存到优先队列，
{
sort(mp,mp+n,cmp1);
for(int i=1;i<n;i++){
man s;
s.u=mp[i-1].id;s.v=mp[i].id;s.w=abs(mp[i-1].x-mp[i].x);
q.push(s);
}//从小到大排序，相邻两个数差距最小
sort(mp,mp+n,cmp2);
for(int i=1;i<n;i++){
man s;
s.u=mp[i-1].id;s.v=mp[i].id;s.w=abs(mp[i-1].y-mp[i].y);
q.push(s);
}
sort(mp,mp+n,cmp3);
for(int i=1;i<n;i++){
man s;
s.u=mp[i-1].id;s.v=mp[i].id;s.w=abs(mp[i-1].z-mp[i].z);
q.push(s);
}
}
void Kruskal() {
ll sumweight=0;//生成树的总权值
int num=0;//已经选用边的数目
int u,v;//顶点
init();
while(1) {
man t=q.top();q.pop();
u=t.u;
v=t.v;
if(Find(u)!=Find(v)) {
sumweight+=t.w;
num++;
Union(u,v);
}
if(num>=n-1) break;//边已经全部建好
}
printf("%lld\n",sumweight);
}
int main() {
memset(vis,false,sizeof(vis));
int u,v,w;
cin>>n;
for(int i=0; i<n; i++){
cin>>mp[i].x>>mp[i].y>>mp[i].z;mp[i].id=i;
}
Build();
Kruskal();
return 0;
}