【题意】
南极有n个科研站， 要把这些站用卫星或者无线电连接起来，使得任意两个都能直接或者间接相连。任意两个都有安装卫星设备的，都可以直接通过卫星通信，不管它们距离有多远。 而安装有无线电设备的两个站，距离不能超过D。 D越长费用越多。
现在有s个卫星设备可以安装，还有足够多的无线电设备，求一个方案，使得费用D最少（D取决与所有用无线电通信的花费最大的那条路径）。
Input
The first line of input contains N, the number of test cases. The first line of each test case contains
1 ≤ S ≤ 100, the number of satellite channels, and S < P ≤ 500, the number of outposts. P lines
follow, giving the (x, y) coordinates of each outpost in km (coordinates are integers between 0 and
10,000).
Output
For each case, output should consist of a single line giving the minimum D required to connect the
network. Output should be specified to 2 decimal points.
Sample Input
1
2 4
0 100
0 300
0 600
150 750
Sample Output
212.13
【分析】
如果没有卫星设备，那就直接最小生成树。
如果卫星设备>=2，那么可以孤立s-1个区域出来（把卫星设备放在那里，剩下一个设备放在大集团里面）
相当于树的s-1条边置为0，
那当然是最小生成树的后s-1大的边置为0咯。
krukal的过程就可以直接计算结果了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 510 struct node
{
int x,y;
double c;
}t[Maxn*Maxn];int len; int nx[Maxn],ny[Maxn]; void ins(int x,int y,double c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
} bool cmp(node x,node y) {return x.c<y.c;} int fa[Maxn];
int ffa(int x)
{
if(x!=fa[x]) fa[x]=ffa(fa[x]);
return fa[x];
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int s,p;
scanf("%d%d",&s,&p);
for(int i=;i<=p;i++) scanf("%d%d",&nx[i],&ny[i]);
len=;
for(int i=;i<=p;i++)
for(int j=i+;j<=p;j++)
{
double xx=(double)(nx[i]-nx[j]),yy=(double)(ny[i]-ny[j]);
ins(i,j,sqrt(xx*xx+yy*yy));
}
sort(t+,t++len,cmp);
int cnt=;
for(int i=;i<=p;i++) fa[i]=i;
if(p==s) printf("0.00\n");
else
{
for(int i=;i<=len;i++)
{
if(ffa(t[i].x)!=ffa(t[i].y))
{
fa[ffa(t[i].x)]=ffa(t[i].y);
cnt++;
if(cnt==p-s) {printf("%.2lf\n",t[i].c);break;}
}
}
} }
return ;
}
2016-11-01 16:35:05