自动搬运

查看原文

来自洛谷，原作者为

	Xeqwq AFOed

搬运于2025-08-24 22:35:43，当前版本为作者最后更新于2022-02-26 22:30:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：最小生成树。

给出 $n$ 个点的三维坐标，可计算出所有点两两之间的距离。
这道题的难点在于存边。
如果 $n$ 个点两两之间的所有边都存下来，那么一共要存 $\frac{n \times (n-1)}{2}$ 条边。
而我们发现数据范围： $n \leqslant 10^{5}$
那么这样我们要存 $5 \times 10^{9}$ 条边，显然会 MLE 。

考虑优化存边方法。
必须删边。
删边，就要删掉那些对于答案没有贡献的边，这些边可有可无。
我们来看一个例子：

3
1 1 1
1 1 2
1 1 3

我们实际上并不需要连三条边，我们只用在第一个点和第二个点、第二个点和第三个点之间各连一条边就可以了。
得出思路：分别按照x、y、z从小到大排三次序，排完后再数组中相邻两项之间建边。
这样我们最多只用建 $3 \times n$ 条边，当 $n=10^{5}$ 时，边数也只会达到 $300000$。

显然这道题建立的是一个稀疏图，我们用 Kruskal 求解最小生成树。
代码奉上：

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;//m为最后的边数
const int Maxn=1e5+5,Maxm=1e6+5;
struct Node//存点，num为点的编号
{
	int x,y,z,num;
}node[Maxn];
struct Edge//存边
{
	int u,v,w;
}graph[Maxm];
//前三个cmp是用在建边时的排序的，最后一个是用在kruskal中的排序的
bool cmpx(Node n1,Node n2) {return n1.x<n2.x;}
bool cmpy(Node n1,Node n2) {return n1.y<n2.y;}
bool cmpz(Node n1,Node n2) {return n1.z<n2.z;}
bool cmpw(Edge e1,Edge e2) {return e1.w<e2.w;}
int fa[Maxn];//并查集优化
int mst;
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y) {fa[find(x)]=find(y);}
void kruskal()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	int count=0;
	sort(graph+1,graph+m+1,cmpw);
	for(int i=1;i<=m;i++)
	{
		Edge e=graph[i];
		int u=e.u,v=e.v,w=e.w;
		if(find(u)!=find(v)) 
		{
			merge(u,v);
			mst+=w;
			count++;
			if(count==n-1) return;
		}
	}
}
void add(int u,int v,int w)
{
	graph[++m].u=u;
	graph[m].v=v;
	graph[m].w=w;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].z);
		node[i].num=i; 
	}
	sort(node+1,node+n+1,cmpx);
	for(int i=1;i<n;i++) add(node[i].num,node[i+1].num,node[i+1].x-node[i].x);
	sort(node+1,node+n+1,cmpy);
	for(int i=1;i<n;i++) add(node[i].num,node[i+1].num,node[i+1].y-node[i].y);
	sort(node+1,node+n+1,cmpz);
	for(int i=1;i<n;i++) add(node[i].num,node[i+1].num,node[i+1].z-node[i].z);
	kruskal();
	cout<<mst;
	return 0;
}