Kruskal - Arctic Network - POJ 2349

Kruskal - Arctic Network - POJ 2349

题目：

$n个村庄(x,y)，要在两两间建立通讯。$

$无限电收发机的参数为d，可以覆盖直线距离在d以内的村庄。$

$卫星设备可以覆盖任意距离的村庄。$

$有k台卫星设备，无限电收发机数量不限。$

$要覆盖n个村庄，问如何分配k台卫星设备，使得使用的无限电收发机的参数d尽量小，输出最小的参数d。$

抽象出题意：

$给定一个n个点的图，两点之间相连通需要一定的花费。$

$可从中选择k个点，这k个点无需花费任何代价即可连通。$

$问最少需要多少代价使得整个图连通。$

$两点之间连通的代价为两点间的欧几里得距离。$

$全图的代价为边权的最大值。$

输入：

$首行输入整数T，共有T组测试数据。$

$每组数据首行包括整数k和n。$

$接着输入n行，表示n个点的坐标。$

输出：

$一个整数，表示最小花费。$

Sample Input

1 2 4 0 100 0 300 0 600 150 750

Sample Output

212.13

数据范围：

$1\le k\le 100，k<n\le 500，0\le x,y\le 10000$

---

分析：

$我们的首要任务是使得n个点连通，在这个前提下，要使得所有边的边权最大值最小。$

$采用kruskal算法，每次添加一条边必然使得图中的连通块数量减少1。$

$通过kruskal算法，优先考虑边权小的边，直到连通块的数量减少到k个，$

$最后对k个连通块，每个连通块中放一个卫星设备，就能够使得全图连通。$

$由于边权是从小到大排序的，最后添加的一条边就是整个图中最长的边，即所求最小的参数d。$

说明：

$在kruskal算法执行的过程中：$

$若从小到大依次添加了前n-k小的边，形成一整个连通块和k个孤立的单点，此时必是最优解。$

$若在考虑某条较小边时生成了环，如果选了这条边，对整个图的连通性无影响，所以不选，放卫星，是最优解。$

$所以kruskal是正确的。$

注意：

$OJ上选择G++与C++提交的注意点：$ 参考：G++与C++的区别。

$另外，本题是多组数据，并查集在使用时，点的编号是从0开始的，所以要初始化p[0]=0。$

代码：

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #define P pair<int,int> #define x first #define y second using namespace std; const int N=510, M=N*N; int n,m,k,T; int p[N]; P V[N]; double res; struct edge { int u,v; double w; bool operator < (const edge &t) const { return w<t.w; } }E[M]; int Find(int x) { if(p[x]!=x) return p[x]=Find(p[x]); return p[x]; } double get_dist(P a,P b) { double dx=a.x-b.x,dy=a.y-b.y; return sqrt(dx*dx+dy*dy); } void kruskal() { sort(E,E+m); int cnt=n; for(int i=0;i<m;i++) //n-k { if(cnt<=k) break; int a=Find(E[i].u),b=Find(E[i].v); if(a!=b) { p[a]=b; res=E[i].w; cnt--; } } } int main() { cin>>T; while(T--) { m=0; cin>>k>>n; for(int i=0;i<=n;i++) p[i]=i; //下面坐标从0开始，所以p[0]也要初始化! for(int i=0;i<n;i++) cin>>V[i].x>>V[i].y; for(int i=0;i<n;i++) for(int j=0;j<i;j++) E[m++]={i,j,get_dist(V[i],V[j])}; kruskal(); printf("%.2f\n",res); } return 0; }