COCI2009/2010 Contest#7 D

[Cost_{a,b}=min(lvert x_a-x_brvert,lvert y_a-y_Brvert,lvert z_a-z_brvert) ]@H_874_11@

​ 其中 (x,y,z) 分别表示星球的坐标。小C想建立 (N-1) 条时空隧道，刚好连接所有星球，并且需要建立隧道的花费尽可能小。作为他的总工程师，你能算出最小的代价么？((1le Nle10^5))

---

​ 建立 (N-1) 条边，刚好连接所有星球，很明显的一个 最小生成树 的题目。我们可以用 Kruskal 来解决这个问题。但是 (N) 太大了一共有 (dfrac{Ntimes(N-1)}{2}) 条边，如果全部存下来，这个数量无论是时间还是空间我们都是无法接受的。我们必须考虑优化，既需要优化空间又需要优化时间，那么最简单直接的方法就是删边，注意到，我们一共只需要 (N-1) 条边，所以我们可以把一些肯定不可能的边删去。思考一下，假如我们要用一条从 (i) 到 (j) 的边，并且他们的边权 (w) 为 (lvert x_i-x_jrvert)，如果存在一个点 (k) 使得 (k) 满足 (min(x_i,x_j)le x_klemax(x_i,x_j)) 那么是不是我们可以以同样的代价连接 (i,k) 与 (j,k)。如果这么连接，不仅代价相同而且产生的一个联通块更大了。但是这种情况一定是最优的吗，毕竟我们多花了一条边去连接。

​ 我们想象一幅图，假设这幅图的最小生成树中有 (i) 到 (j) 这条边。我们把这条边去掉，换成 (i) 到 (k)，(k) 到 (j) 这两条边，由于原图是一个最小生成树 ,(i,j,k) 在原图中肯定是通过某些边相连的，我们设 (k) 与 (q) 相连，且 (q) 通过一系列边与 (i,j) 相连。显然，我们去掉 (k) 与 (q) 相连的这条边，那么图中又只有 (n-1) 条边了。显然，这幅图还是一幅连通图，而且代价会更小(或者相等)。于是我们可以得出结论：在本题的条件下，代价相同的情况下，所能产生的联通快越大越好。

​ 那么我们可以以三维来排序，一共排三次，每次排完都将相邻的两个点连一条边。意思是：我们先以 (X) 排序（使用结构体连编号一起排序），然后对于任意的 (i) 我们连一条从 (id_i) 到 (id_{i-1})，边权为 (lvert x_i-x_{i-1}rvert) 的边，然后再以 (y) 排序，以此类推。我们这么连接的边可能有些权值不符合题设，但是连出来的边一定都大于题设边的权值。如果我们使用了不符合题设的边作为答案，那么它一定可以被符合题设的边替代。所以算出来的答案不会偏大。具体细节看看代码。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
int n;
struct node
{
	ll x;
	int id;
	bool operator < (const node &a)const
	{
		return x<a.x;
	}
}x[MAXN],Y[R_673_11845@AXN],z[MAXN];
struct edge
{
	ll w;
	int u,v;
	bool operator < (const edge &X)const
	{
		return w<x.w;
	}
}e[MAXN<<2];
int tot;
void add(int i,int j)
{
	e[++tot].w=abs(x[i].x-x[j].X);
	e[tot].u=x[i].id,e[tot].v=x[j].id;
	
	e[++tot].w=abs(Y[i].x-Y[j].X);
	e[tot].u=Y[i].id,e[tot].v=Y[j].id;
	
	e[++tot].w=abs(z[i].x-z[j].X);
	e[tot].u=z[i].id,e[tot].v=z[j].id;
}
int f[MAXN];
int find(int X)
{
	if(x==f[x]) return x;
	else return f[x]=find(f[x]);
}
ll kruskal()
{
	ll ans=0;
	sort(e+1,e+1+tot);
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=1;i<=tot;++i)
	{
		int u=e[i].u,v=e[i].v;
		ll w=e[i].w;
		if(find(u)==find(v)) conTinue;
		ans+=w;
		f[find(u)]=find(v);
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld %lld %lld",&x[i].x,&Y[i].x,&z[i].X);
		x[i].id=Y[i].id=z[i].id=i;
	}
	sort(x+1,x+1+n);sort(y+1,y+1+n);sort(z+1,z+1+n);
	for(int i=2;i<=n;++i)
		add(i,i-1);
	printf("%lld",kruskal());
	return 0;
}

总结：

​ 这题删边的思想还是比较妙的，碰到时间空间都超限的题目就可以尝试这种方法，将必定无用的状态删去以节省空间与时间。

大佬总结

以上是大佬教程为你收集整理的COCI2009/2010 Contest#7 D全部内容，希望文章能够帮你解决COCI2009/2010 Contest#7 D所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。