北极的某区域共有 n 座村庄，每座村庄的坐标用一对整数 (x,y) 表示。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。
不同型号的无线电收发机有一个不同的参数 ddd，两座村庄之间的距离如果不超过 ddd 就可以用该型号的无线电收发机直接通讯，ddd 值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。
现在有 kkk 台卫星设备，请你编一个程序，计算出应该如何分配这 kkk 台卫星设备，才能使所拥有的无线电收发机的 ddd 值最小，并保证每两座村庄之间都可以直接或间接地通讯。
例如，对于下面三座村庄：
其中 |AB|=10,|BC|=20,|AC|=10√5≈22.36
如果没有任何卫星设备或只有 111 台卫星设备 (k=0k=0k=0 或 k=1k=1k=1)，则满足条件的最小的 d=20d = 20d=20，因为 AAA 和 BBB，BBB 和 CCC 可以用无线电直接通讯；而 AAA 和 CCC 可以用 BBB 中转实现间接通讯 (即消息从 AAA 传到 BBB，再从 BBB 传到 CCC)；
如果有 222 台卫星设备 (k=2k=2k=2)，则可以把这两台设备分别分配给 BBB 和 CCC ，这样最小的 ddd 可取 101010，因为 AAA 和 BBB 之间可以用无线电直接通讯；BBB 和 CCC 之间可以用卫星直接通讯；AAA 和 CCC 可以用 BBB 中转实现间接通讯。
如果有 333 台卫星设备，则 A,B,CA,B,CA,B,C 两两之间都可以直接用卫星通讯，最小的 ddd 可取 000。
已经是一年前做的题了，今天又遇到，算是缘分吧
曾今的代码风格还稍显稚嫩，还不会写read和write，变量名字也起的是同学名字的首字母，有一些已经退役了
首先是两两连边，然后直接最小生成树
下面给出代码：
#include<iostream>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<cstdio>#include<cstdlib>using namespace std;inline long long rd(){ ???long long x=0,f=1; ???char ch=getchar(); ???for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=-1; ???for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; ???return x*f;}inline void write(int x){ ???if(x<0) putchar(‘-‘),x=-x; ???if(x>9) write(x/10); ???putchar(x%10+‘0‘); ???return ;}int x[10000],y[10000],f[100000];double road[100000];struct node{ ???int a,b,c; ???double wht;}map[1000000]; ?void whtsort(int l,int r){ ???int i,j; ???node t; ???if(l>r) ???????return ; ???i=l; ???j=r; ???while(i!=j){ ???????while(map[j].wht>=map[l].wht&&i<j) j--; ???????while(map[i].wht<=map[l].wht&&i<j) i++; ???????if(i<j){ ???????????t=map[i]; ???????????map[i]=map[j]; ???????????map[j]=t; ???????} ???} ???t=map[l]; ???map[l]=map[i]; ???map[i]=t; ???whtsort(l,i-1); ???whtsort(i+1,r); ???return ;}double hhd(double a1,double b1,double a2,double b2){ ???double aa=a1-a2,bb=b1-b2; ???double hh=sqrt((aa*aa)+(bb*bb)); ???return hh;}int getf(int hh){ ???if(f[hh]==hh) return hh; ???else return f[hh]=getf(f[hh]);}int merge(int xx,int yy){ ???int t1,t2; ???t1=getf(xx); ???t2=getf(yy); ???if(t1!=t2){ ???????f[t2]=t1; ???????return 1; ???} ???return 0;}int main(){ ???int n=0,m=0,i=0,j=0,k=1,count=0; ???m=rd(),n=rd(); ???for(i=1;i<=m;i++){ ???????x[i]=rd(),y[i]=rd(); ???????for(j=1;j<i;j++){ ???????????map[k].wht=hhd(x[i],y[i],x[j],y[j]); ???????????map[k].a=i; ???????????map[k].b=j; ???????????k++; ???????} ???} ???whtsort(1,k); ???for(i=1;i<=m;i++)f[i]=i; ???for(i=1;i<=k;i++){ ???????if(merge(map[i].a,map[i].b)==1){ ???????????road[count]=map[i].wht; ???????????count++; ???????} ???} ???printf("%.2f\n",road[count-n]); ???return 0;}
Poj2349 Arctic Network ?（北极通讯网络）
原文地址：https://www.cnblogs.com/WWHHTT/p/9845664.html