poj2349:Arctic Network(最小生成树)

题意：有n个点给出坐标，点和点之间可以用无线电或者卫星通信，每个点都有无线电收发器可进行无线电通信，但是只有m个点有卫星通信功能。卫星通信的距离可以无限大，但无线电通信的距离不能超过D，超过D的部分将使通信费用增加。要使通信费用最少。

其实就是求一次最小生成树，m个点有卫星通信，那么就会有m-1条边的通信距离无限大，其实就是这m-1条边不用计算费用。而剩下的边中，找出最大边作为D值，这样剩下的所有的边都不会大于D，那么不会增加通信费用。在构建MST过程中保存下所有的边权值，然后按升序排序，除掉最后的m-1条边（也就是最大的m-1条边，这些边用卫星通信），最大的那条就是D；附ac代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct node
{
	int start;
	int end;
	double cost;
}t[1001000];
int cmp(node a,node b)
{
	return a.cost <b.cost ;
}
int per[1100];
int find(int x)
{
	int r=x;
	while(r!=per[r])
	r=per[r];
	return r;
}
int join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
		per[fx]=fy;
		return 1;
	}
	return 0;
}
int main()
{
	int k,m,n,p,i,j;
	int x[110010],y[110010];
	scanf("%d",&p);
	while(p--)
	{
		for(i=0;i<1100;i++)
		per[i]=i;
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
		k=0;
		for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			t[k].start=i;
			t[k].end =j;
			t[k].cost =sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
			k++;
		}
		sort(t,t+k,cmp);
		int v=0;
		double ans;
		for(i=0;i<k;i++)
		{
			if(join(t[i].start,t[i].end))
			v++;
			if(v==n-m)
			{
				ans=t[i].cost;
				break;
			}
		}
		printf("%.2f\n",ans);
	}
  return 0;
}