沈阳做网站哪家质量好价格低,网站建设合同合同期限,商城网站建站程序,爱用建站 小程序北极的某区域共有 n 座村庄#xff0c;每座村庄的坐标用一对整数 (x,y) 表示。
为了加强联系#xff0c;决定在村庄之间建立通讯网络#xff0c;使每两座村庄之间都可以直接或间接通讯。
通讯工具可以是无线电收发机#xff0c;也可以是卫星设备。
无线电收发机有多种不…北极的某区域共有 n 座村庄每座村庄的坐标用一对整数 (x,y) 表示。
为了加强联系决定在村庄之间建立通讯网络使每两座村庄之间都可以直接或间接通讯。
通讯工具可以是无线电收发机也可以是卫星设备。
无线电收发机有多种不同型号不同型号的无线电收发机有一个不同的参数 d两座村庄之间的距离如果不超过 d就可以用该型号的无线电收发机直接通讯d 值越大的型号价格越贵。现在要先选择某一种型号的无线电收发机然后统一给所有村庄配备数量不限但型号都是 相同的。
配备卫星设备的两座村庄无论相距多远都可以直接通讯但卫星设备是 有限的只能给一部分村庄配备。
现在有 k 台卫星设备请你编一个程序计算出应该如何分配这 k 台卫星设备才能使所配备的无线电收发机的 d 值最小。
例如对于下面三座村庄 其中|AB|10,|BC|20,|AC|105√≈22.36
如果没有任何卫星设备或只有 1 台卫星设备 (k0或 k1)则满足条件的最小的 d20因为 A 和 BB 和 C 可以用无线电直接通讯而 A 和 C 可以用 B 中转实现间接通讯 (即消息从 A 传到 B再从 B 传到 C)
如果有 2 台卫星设备 (k2)则可以把这两台设备分别分配给 B 和 C 这样最小的 d 可取 10因为 A 和 B 之间可以用无线电直接通讯B 和 C 之间可以用卫星直接通讯A 和 C 可以用 B 中转实现间接通讯。
如果有 3 台卫星设备则 A,B,C 两两之间都可以直接用卫星通讯最小的 d 可取 0。
输入格式
第一行为由空格隔开的两个整数 n,k
接下来 n 行每行两个整数第 i 行的 xi,yi表示第 i 座村庄的坐标 (xi,yi)。
输出格式
一个实数表示最小的 d 值结果保留 2 位小数。
数据范围
1≤n≤500 0≤x,y≤104 0≤k≤100
输入样例
3 2
10 10
10 0
30 0输出样例
10.00难度中等时/空限制1s / 64MB总通过数5213总尝试数12579来源《信息学奥赛一本通》 , Waterloo University 2002算法标签
解析
性质建立一棵最小生成树将最大的k个边去掉剩下的边中的最大权值就是答案
具体操作我们可以在使用Kruskal算法时记录一下连通分量的个数当连通分量的个数k
时此时图中最大的边的权值就是答案
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemapusing namespace std;
#define x first
#define y second
typedef long long LL;
const int N 5e2 5,MN*N/2;
typedef pairint, intPII;
int n, k;
struct e {int a, b;double c;
}e[M];
PII p[N];
int fa[N];double getdist(PII a, PII b) {double dx a.first - b.first;double dy a.second - b.second;return sqrt(fabs(dx * dx dy * dy));
}int cmp(const struct e a, const struct e b) {return a.c b.c;
}int find(int a) {if (fa[a] a)return a;return fa[a] find(fa[a]);
}int main() {cin n k;for (int i 1; i n; i) {scanf(%d%d, p[i].x, p[i].y);}int m 0;for (int i 1; i n; i) {for (int j 1; j i; j) {e[m] { i,j,getdist(p[i],p[j])};}}for (int i 1; i n; i) {fa[i] i;}sort(e 1, e 1 m, cmp);int cnt n;double maxd 0;for (int i 1; i m; i) {if (cnt k) {break;}int a find(e[i].a), b find(e[i].b);double d e[i].c;if (a ! b) {fa[a] b;cnt--;maxd d;}}printf(%.2lf\n, maxd);return 0;
}
