poj_2349 Kruskal 最小生成树

题目大意

    给定N个点的坐标，这N个点之间需要进行通讯。通讯方式可以采用卫星通信或无线通信，若两点之间采用为卫星通信，则两点之间的距离无限制，若采用无线通讯，则两点之间的距离不能大于某个值D。 
    现有s台卫星通信设备可以分配给这N个点，其余的点之间必须使用无线通信。要让这N个点中所有的点都能相互通信，则合理分配s台卫星通信设备，可以使得采用无线通信的那些点之间的距离D达到一个最小值，求该最小值。

题目分析

    让所有的点之间均能通信，为一个生成树结构。题目就是求出这N个点的最小生成树。然后将最小生成树分成S个割集，割集之间采用卫星通信，割集之内采用无线通信，求出割集之内点之间的最大值即可。 
    可以证明，割集之内的点距离的最大值的最小值为最小生成树的N-1条边从大到小排列后第S个边长。采用kruskal算法解决。

实现(c++)

#include<stdio.h>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
#define MAX_NODE 505
//点的数据结构
struct Point{
	int x;
	int y;
};
vector<Point> gPoints;

//边的数据结构
struct Edge{
	int from;
	int to;
	double dist;
	Edge(int f, int t, double d) :
		from(f), to(t), dist(d){};
};
vector<Edge> gEdges;

//计算两点之间的距离
double Dist(const Point& p1, const Point& p2){
	return sqrt(1.0*(p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

//用并查集来判断加入一条边是否会构成环
int gRoot[MAX_NODE];
int GetRoot(int c){
	if (gRoot[c] != c){
		gRoot[c] = GetRoot(gRoot[c]);
	}
	return gRoot[c];
}
bool SameRoot(int c1, int c2){
	int p1 = GetRoot(c1);
	int p2 = GetRoot(c2);
	return p1 == p2;
}

void Union(int c1, int c2){
	int p1 = GetRoot(c1);
	int p2 = GetRoot(c2);
	gRoot[p1] = p2;
}
//用于对边进行排序
bool Compare(const Edge& e1, const Edge& e2){
	return e1.dist < e2.dist;
}


double Kruskal(int s, int n){
	double result;
	for (int i = 0; i < n; i++){
		gRoot[i] = i;
	}
	sort(gEdges.begin(), gEdges.end(), Compare); //无向图的边只存储了 从序号较小的节点指向序号较大的节点
	int count = 0;
	for (int i = 0; i < gEdges.size(); i++){
		Edge& e = gEdges[i];
		if (SameRoot(e.from, e.to))
			continue;

		count++;
		if (count == n - s){ 
			//从最小生成树中的n-1条边，去掉最大的s-1条边（因为有s个卫星站，相当于s个点，则s-1条边）
			//，剩下的n-1-s条边中，最大的边长即为所求
			result = e.dist;
			return result;
		}
		
		Union(e.to, e.from);
		//gRoot[gRoot[e.to]] = gRoot[e.from]; //注意合并的时候，将 to 的根更新为 from的根。因为所有的边只存储了从小序号指向大序号
	}
	return 0;
}

int main(){
	int cas, s, p;
	Point point;
	scanf("%d", &cas);
	while (cas--){
		scanf("%d %d", &s, &p);
		gEdges.clear();
		gPoints.clear();
		for (int i = 0; i < p; i++){
			scanf("%d %d", &point.x, &point.y);
			for (int j = 0; j < i; j++){
				double dist = Dist(point, gPoints[j]);
				gEdges.push_back(Edge(j, i, dist));
			}
			gPoints.push_back(point);
		}
		double result = Kruskal(s, p);
		printf("%.2lf
", result);
	}
	return 0;
}