[Poj2349]Arctic Network

Description

国防部（DND）要用无线网络连接北部几个哨所。两种不同的通信技术被用于建立网络：每一个哨所有一个无线电收发器，一些哨所将有一个卫星频道。

任何两个有卫星信道的哨所可以通过卫星进行通信，而不管他们的位置。同时，当两个哨所之间的距离不超过D时可以通过无线电通讯，D取决于对收发器的功率。功率越大，D也越大，但成本更高。出于采购和维修的方便，所有哨所的收发器必须是相同的；那就是说，D值对每一个哨所相同。

你的任务是确定收发器的D的最小值。每对哨所间至少要有一条通信线路（直接或间接）。

Input

输入的第一行是测试数据的数量N。

每组测试数据的第一行包含卫星频道的数量S（1 < = S < = 100）和哨所的数量P（S < P < = 500）。接下来的P行，给出以公里为单位的每个哨所的坐标(x,y)( 坐标为0到10000之间的整数)。

Output

对于每组测试数据，输出一行，输出收发器的D的最小值。精确到小数点后两位。

Sample Input

1

2 4

0 100

0 300

0 600

150 750

Sample Output

212.13

不算很难的题目，在这里使用的二分，每次二分出最大值，跑一次最小生成树，判断联通块个数是否>k。时间复杂度：\(O(Tnlogn)\)

这道题还有另一种做法，先直接跑一次最小生成树，然后找到生成树上第k+1大的边。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

	int x=0,w=1;char ch=getchar();

	while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return x*w;

}

const int N=510;

int n,k,cnt;double l,r,mid;

int x[N],y[N],fa[N];

struct node{

	int x,y;double v;

}f[N*N];

int gfa(int x){if(x==fa[x])return x;return fa[x]=gfa(fa[x]);}

bool cmp(node p,node q){return p.v<q.v;}

bool check(double v)

{

	int qwe=0,num=0;

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1;i<=cnt;i++)

	{

		if(f[i].v>v) break;

		int xx=gfa(f[i].x),yy=gfa(f[i].y);if(xx==yy)continue;

		fa[xx]=yy;qwe++;if(qwe==n-1) break;

	}

	for(int i=1;i<=n;i++) if(fa[i]==i)num++;

	return num<=k;

}

int main()

{

	int t=read();

	while(t--)

	{

		cnt=0;k=read();n=read();

		for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();

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

		for(int j=i+1;j<=n;j++)

		{

			double dis=sqrt((double)(y[i]-y[j])*(y[i]-y[j])+(x[i]-x[j])*(x[i]-x[j]));

			f[++cnt].x=i;f[cnt].y=j;f[cnt].v=dis;

		}

		sort(f+1,f+1+cnt,cmp);

		l=0;r=100000;

		while(r-l>1e-4)

		{

			mid=(l+r)/2;

			if(check(mid)) r=mid;

			else l=mid;

		}

		printf("%.2lf\n",r);

	}

	return 0;

}