kd树模板+全图最小生成树

标签（空格分隔）： kd树+最小生成树

题意： k维太空中有n个点，每个点可以与距离它m近的点连边，现在给你一堆点，并给出坐标，现在要建立通信网络，一些可以互相到达的点构成一个group，现在要求每个组中的最长的边的权值最小，输出组数，和最长边的最小权值数。

题解：求一个k维空间的距离某个点的前m近点很明显可以使用kd树。权值最小，很明显用最小生成树来优化全局图，最后根据其公共父节点来算一共几个组即可。

kd树讲解及模板：

kd树通过划分平面来建树，对于每个维度，都以位于中间节点的位置划分，注意，如果有其他和这个中间节点坐标相同的点将会被划分到左区间。

下面给出kd树有注释的讲解代码，和没有注释的模板代码：

const int K = 5;//维度

int n,m,idx;

struct Point {

	int id;//节点编号

	int x[K];//对应每一个维度的坐标

	bool operator < (const Point &u) const {

		return x[idx]<u.x[idx];//按照第idx维坐标从小到大排列

	}

}po[Maxn];

double pow(double x){

	return 1.0*x*x;

}

double pow(int x){

	return 1.0*x*x;

}

struct PDP{

	double dis;//距离目标点的距离

	Point p;//这个点

	bool operator<(const PDP pdp) const{

		if(dis!=pdp.dis) return dis< pdp.dis;

		else {

			for(int i = 0; i < K; i++)

				if(p.x[i] != pdp.p.x[i]) return p.x[i] < pdp.p.x[i];

			return false;

		}

	}//按照距离排序，距离一样按照每一维度的从小到大排列

	PDP (double _dis,Point _p)

	{

		dis = _dis;

		p = _p;

	}//构造函数

};

priority_queue<PDP> nq;//优先队列保存于跟新距离某个点距离第k大的这些点

struct Tree{//kd树，因为一定是二叉树，所以可以用编号保存树

	Point p[Maxn<<2];//树的节点

	int son[Maxn<<2];//每个节点的孩子个数，用来判断是否到达根节点

	void build (int l, int r, int u = 1, int dep = 0)//建树

	{

		if(l>r) return;

		son[u] = r-l;

		son[u<<1] = son[u<<1|1] = -1;

		idx = dep%K;//维度划分方式

		int mid = (l+r)>>1;//以中间点来划分树

		nth_element(po+l,po+mid,po+r+1);//比mid对应第idx维度下的坐标小的都在左边，大的在右边。

		p[u] = po[mid];//定义节点的编号

		build(l,mid-1,u<<1,dep+1);

		build(mid+1,r,u<<1|1,dep+1);

	}

	void query(Point a, int m, int u = 1, int dep = 0)//查询距离a前m大的数

	{

		if(son[u]==-1) return ;

		PDP nd(0,p[u]);//判断根节点

		for(int i = 0; i < K; i++)

			nd.dis += pow(nd.p.x[i]-a.x[i]);//计算根节点到节点a的距离

		int dim = dep%K, fg = 0;//当前维度和是否需要继续向下判断

		int x = u<<1, y = u<<1|1;//左右孩子，每次都是先判断左孩子

		if(a.x[dim]>=p[u].x[dim]) swap(x,y);//如果这个点位于根节点的左孩子，那么先找左孩子肯定比较更容易找到解

		if(~son[x]) query(a,m,x,dep+1);//如果左孩子的值不等于-1即不空则查询左区间

		if(nq.size() < m) nq.push(nd),fg = 1;//如果队列中不足m个元素，则把这个点加入队列

		else {

			if(nd.dis < nq.top().dis) nq.pop(),nq.push(nd);//如果这个点的距离比当前队列中最大的那个还要小，则替换最大的

			if(pow(a.x[dim]-p[u].x[dim]) < nq.top().dis) fg = 1;//如果在这个维度上a距离分界点的距离都要大于队列中m个元素距离a的距离则没有必要再搜索右子树了。相反要搜索右子树，fg = 1;

		}

		if(~son[y] && fg) query(a,m,y,dep+1);//右子树不空且有必要搜索右子树时候搜索右子树

	}

}kd;

kd树模板

const int K = 5;

int n,m,idx;

struct Point {

	int id;

	int x[K];

	bool operator < (const Point &u) const {

		return x[idx]<u.x[idx];

	}

}po[Maxn];

double pow(double x){

	return 1.0*x*x;

}

double pow(int x){

	return 1.0*x*x;

}

struct PDP{

	double dis;

	Point p;

	bool operator<(const PDP pdp) const{

		if(dis!=pdp.dis) return dis< pdp.dis;

		else {

			for(int i = 0; i < K; i++)

				if(p.x[i] != pdp.p.x[i]) return p.x[i] < pdp.p.x[i];

			return false;

		}

	}

	PDP (double _dis,Point _p)

	{

		dis = _dis;

		p = _p;

	}

};

priority_queue<PDP> nq;

struct Tree{

	Point p[Maxn<<2];

	int son[Maxn<<2];

	void build (int l, int r, int u = 1, int dep = 0)

	{

		if(l>r) return;

		son[u] = r-l;

		son[u<<1] = son[u<<1|1] = -1;

		idx = dep%K;

		int mid = (l+r)>>1;

		nth_element(po+l,po+mid,po+r+1);

		p[u] = po[mid];

		build(l,mid-1,u<<1,dep+1);

		build(mid+1,r,u<<1|1,dep+1);

	}

	void query(Point a, int m, int u = 1, int dep = 0)

	{

		if(son[u]==-1) return ;

		PDP nd(0,p[u]);

		for(int i = 0; i < K; i++)

			nd.dis += pow(nd.p.x[i]-a.x[i]);

		int dim = dep%K, fg = 0;

		int x = u<<1, y = u<<1|1;

		if(a.x[dim]>=p[u].x[dim]) swap(x,y);

		if(~son[x]) query(a,m,x,dep+1);

		if(nq.size() < m) nq.push(nd),fg = 1;

		else {

			if(nd.dis < nq.top().dis) nq.pop(),nq.push(nd);

			if(pow(a.x[dim]-p[u].x[dim]) < nq.top().dis) fg = 1;

		}

		if(~son[y] && fg) query(a,m,y,dep+1);

	}

}kd;

下面是这个题的ac代码

//kd树+最小生成树

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<iostream>

#include<cmath>

#define Maxn 20008

#define Maxm 500008

using namespace std;

const int K = 5;//维度

int n,m,idx;

struct Point {

	int id;//节点编号

	int x[K];//对应每一个维度的坐标

	bool operator < (const Point &u) const {

		return x[idx]<u.x[idx];//按照第idx维坐标从小到大排列

	}

}po[Maxn];

double pow(double x){

	return 1.0*x*x;

}

double pow(int x){

	return 1.0*x*x;

}

struct PDP{

	double dis;//距离目标点的距离

	Point p;//这个点

	bool operator<(const PDP pdp) const{

		if(dis!=pdp.dis) return dis< pdp.dis;

		else {

			for(int i = 0; i < K; i++)

				if(p.x[i] != pdp.p.x[i]) return p.x[i] < pdp.p.x[i];

			return false;

		}

	}//按照距离排序，距离一样按照每一维度的从小到大排列

	PDP (double _dis,Point _p)

	{

		dis = _dis;

		p = _p;

	}//构造函数

};

priority_queue<PDP> nq;//优先队列保存于跟新距离某个点距离第k大的这些点

struct Tree{//kd树，因为一定是二叉树，所以可以用编号保存树

	Point p[Maxn<<2];//树的节点

	int son[Maxn<<2];//每个节点的孩子个数，用来判断是否到达根节点

	void build (int l, int r, int u = 1, int dep = 0)//建树

	{

		if(l>r) return;

		son[u] = r-l;

		son[u<<1] = son[u<<1|1] = -1;

		idx = dep%K;//维度划分方式

		int mid = (l+r)>>1;//以中间点来划分树

		nth_element(po+l,po+mid,po+r+1);//比mid对应第idx维度下的坐标小的都在左边，大的在右边。

		p[u] = po[mid];//定义节点的编号

		build(l,mid-1,u<<1,dep+1);

		build(mid+1,r,u<<1|1,dep+1);

	}

	void query(Point a, int m, int u = 1, int dep = 0)//查询距离a前m大的数

	{

		if(son[u]==-1) return ;

		PDP nd(0,p[u]);//判断根节点

		for(int i = 0; i < K; i++)

			nd.dis += pow(nd.p.x[i]-a.x[i]);//计算根节点到节点a的距离

		int dim = dep%K, fg = 0;//当前维度和是否需要继续向下判断

		int x = u<<1, y = u<<1|1;//左右孩子，每次都是先判断左孩子

		if(a.x[dim]>=p[u].x[dim]) swap(x,y);//如果这个点位于根节点的左孩子，那么先找左孩子肯定比较更容易找到解

		if(~son[x]) query(a,m,x,dep+1);//如果左孩子的值不等于-1即不空则查询左区间

		if(nq.size() < m) nq.push(nd),fg = 1;//如果队列中不足m个元素，则把这个点加入队列

		else {

			if(nd.dis < nq.top().dis) nq.pop(),nq.push(nd);//如果这个点的距离比当前队列中最大的那个还要小，则替换最大的

			if(pow(a.x[dim]-p[u].x[dim]) < nq.top().dis) fg = 1;//如果在这个维度上a距离分界点的距离都要大于队列中m个元素距离a的距离则没有必要再搜索右子树了。相反要搜索右子树，fg = 1;

		}

		if(~son[y] && fg) query(a,m,y,dep+1);//右子树不空且有必要搜索右子树时候搜索右子树

	}

}kd;

void print(Point &a)

{

	for(int j = 0; j < K; j++)

		printf("%d%c",a.x[j],j==K-1?'\n':' ');

}

double E[Maxn];

int Ecnt,fa[Maxn];

int getfa(int x)

{

	if(fa[x]==x) return x;

	return fa[x] = getfa(fa[x]);

}

struct Edge{

	int u,v;

	double cost;

	bool operator <(const Edge e) const{

		if(cost != e.cost) return cost < e.cost;

		else if(u!=e.u) return u<e.u;

		else if(v!=e.v) return v<e.v;

		return false;

	}

}edge[Maxm];//存图，保存所有的边

void add(int u, int v, double cost){

	edge[Ecnt].u = u,edge[Ecnt].v = v,edge[Ecnt++].cost = cost;

}

bool cmp(Edge a, Edge b)

{

	return a.cost < b.cost;

}

double Kruskal(int n,int m)

{

	int u,v,x;

	double cost, ans = 0;

	sort(edge,edge+m,cmp);

	for(u = 0; u < n; u++) fa[u] = u,E[u] = -1;

	for(int i = 0; i < m; i++){

		u = edge[i].u, v = edge[i].v, cost = edge[i].cost;

		if(getfa(u) == getfa(v)) continue;

		ans += cost;

		E[u] = max(E[u],cost);

		E[v] = max(E[v],cost);

		fa[fa[u]] = fa[v];

	}

	return ans;

}//最小生成树

vector<int> ve[Maxn];

void init()

{

	Ecnt = 0;

	for(int i = 0; i < n; i++)	ve[i].clear();

}

inline double dis(Point _A, Point _B)

{

	double ret = 0;

	for(int i = 0; i < K; i++) ret += pow(_A.x[i]-_B.x[i]);

	return sqrt(ret);

}

double result[Maxn];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d %d",&n,&m);

		for(int i = 0; i < n; i++){

			po[i].id = i;

			for(int j = 0; j < K; j++)

				scanf("%d",&po[i].x[j]);

		}

		kd.build(0,n-1);

		init();

		for(int i = 0; i < n; i++)

		{

			kd.query(po[i],min(m+1,n));

			int ori = po[i].id;

			for(int j = 0; !nq.empty();j++){

				Point tm = nq.top().p;

				nq.pop();

				double cost = dis(po[i],tm);

				if(ori != tm.id) add(ori,tm.id,cost);

			}

		}

		Kruskal(n,Ecnt);

		for(int i = 0; i < n; i++) result[i] = -1;

		for(int i = 0; i < n; i++) {

			int id = getfa(i);

			result[id] = max(result[id],E[i]);

		}

		sort(result,result+n);

		int num = n,t;

		for(t = 0; t < n; t++){

			if(result[t] <= 0) num--;

			else break;

		}

		printf("%d\n",num);

		for(; t<n; t++){

			printf("%lf",result[t]);

			if(t<n-1) printf(" ");

		}

		puts("");

	}

	return 0;

}

巴特西

tju_4147 kd树+最小生成树

kd树模板+全图最小生成树

最新文章

热门文章