【题目描述】原题来自：Waterloo University 2002北极的某区域共有 n 座村庄，每座村庄的坐标用一对整数 (x,y) 表示。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数 d，两座村庄之间的距离如果不超过 d 就可以用该型号的无线电收发机直接通讯，d 值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有 k 台卫星设备，请你编一个程序，计算出应该如何分配这 k 台卫星设备，才能使所拥有的无线电收发机的 d 值最小，并保证每两座村庄之间都可以直接或间接地通讯。例如，对于下面三座村庄：其中 |AB|=10,|BC|=20,|AC|=10√5≈22.36如果没有任何卫星设备或只有 1 台卫星设备 (k=0 或 k=1)，则满足条件的最小的 d=20，因为 A 和 B，B 和 C 可以用无线电直接通讯；而 A 和 C 可以用 B 中转实现间接通讯 (即消息从 A 传到 B，再从 B 传到 C)；如果有 2 台卫星设备 (k=2)，则可以把这两台设备分别分配给 B 和 C ，这样最小的 d 可取 10，因为 A 和 B 之间可以用无线电直接通讯；B 和 C 之间可以用卫星直接通讯；A 和 C 可以用 B 中转实现间接通讯。如果有 3 台卫星设备，则 A,B,C 两两之间都可以直接用卫星通讯，最小的 d 可取 0。【输入】第一行为由空格隔开的两个整数 n,k;第 2∼n+1 行，每行两个整数，第 i 行的 xi,yi 表示第 i 座村庄的坐标 (xi,yi)。【输出】一个实数，表示最小的 d 值，结果保留 2 位小数。【输入样例】3 2 10 10 10 0 30 0【输出样例】10.00【提示】数据范围:对于全部数据，1≤n≤500,0≤x,y≤10^4,0≤k≤100。1. 题意转换用一句话剥离题目的“北极、村庄、卫星”的包装故事：给定平面上的N个点，求将其划分为k个连通块（即构建一棵包含k棵树的最小生成森林）时，各连通块内部所有边的最大值中的最小值（最小瓶颈边）。2. 思考过程与解题思路面对这道题，第一直觉是什么？很多同学看到“通讯网络”、“连通”、“最大距离最小”，直觉可能是二分答案：二分出一个距离d，然后用 BFS/DFS 检查在这个距离下，图是否能形成个连通块。这种做法时间复杂度约为 O(N^2 log(值域))，虽然能过，但在处理浮点数二分时极易遭遇精度死循环（TLE或WA）。考点锁定：关键字：“保证直接或间接通讯”、“使最大的d最小”。这简直是把kruskal算法的“最小瓶颈生成树”特性贴在了脸上。Kruskal 算法不仅能求出边权总和最小的生成树，它找出来的树还自带神级属性：它包含的最大那条边，在所有可能让图连通的方案中，绝对是最小的！如何一步步推导到正解？没有卫星时（k=0或1）：我们需要用无线电把N个村庄连成1棵完整的大树，此时恰好需要连接N-1条边。有k台卫星时（）：卫星堪称“神级网线”，无论多远都能瞬间连通。如果我们把这k台卫星分别发给k个互相独立的连通分量，卫星就能在云端把它们免费缝合起来。核心数学映射：我们的无线电不再需要把图连成 1 棵树，只需要把N个孤立的村庄连成k个连通分量（也就是一片包含k棵树的森林）。在图论中，从N个点合并且只剩k个连通块，恰好需要成功连接N-k条边。得出结论：因为 Kruskal 是按边长从小到大贪心加边的。当我们成功加上第N-k条边时，这片森林刚刚好建成，而这最后加进去的第N-k条边，必然是网络中最长的一条边，它的长度就是题目要求的最小的d。3. 算法设计与样例推演核心逻辑与数据结构：坐标与距离计算：用结构体存点，双重循环计算任意两点间的欧几里得距离，构建完全图（跳过重复边）。边集数组edge：存储两点及距离平方（避免浮点精度问题）。并查集（DSU）：用于 Kruskal 贪心加边时的判环和合并。极简数据手玩推演：带入题目样例：N=3 座村庄，k=2 台卫星。目标边数：N-k = 3-2 = 1条边。建边与排序：AB距离为 10，BC为 20，AC约为 22.36。排序后：AB(10)BC(20)AC(22.36)。Kruskal 连线：取出最短边 AB，A 和 B 不在同一连通块，合并它们。此时成功连接了 1 条边。判定结束：已达到目标边数 1！最后加进去的边长是 10，直接输出 10.00。与样例完全吻合！4. 时空复杂度分析时间复杂度：。，建完全图会产生约条边，即。Kruskal 的瓶颈在sort，复杂度为，约执行次运算，C++ 在 1 秒内极其轻松过关。空间复杂度：。需要一个长度为M的边集数组。即便开到 500010，也仅占用十几 MB 的内存，远低于题目要求的 64MB 限制。5. 坑点与易错总结浮点数排序丢失精度（极易 WA）：如果在结构体里直接存sqrt开方后的double距离，在sort比较时极易遇到浮点数尾数精度丢失导致的排序错乱。（本题代码完美避开了这一点，后文详述）特判遗漏（极易 RE/WA）：如果卫星比村庄还多（），或者只有一个村庄（N=1），此时不需要连任何边，应当直接输出0.00并结束程序。无向图重复建边拖慢常数：建图时如果写i!=j会把边存两遍，导致sort的常数翻倍。必须用j>i来只存右上三角矩阵。6. 代码进阶与优化剖析（核心教学点）这篇题解的代码是一份几近完美的标程，其中展现了两个极高阶的竞赛编码习惯，强烈建议所有备考 CSP 的同学刻在 DNA 里：高阶技巧 1：延迟开方（降维打击精度问题）仔细看代码：long long val; //存边长的平方 避免开方过程中产生精度问题。作者极其聪明地在sort时比较的是距离的平方（绝对精度的整数），完全避免了引入double。直到程序最后一行输出答案时，才对其使用一次sqrt。这不仅避免了任何精度被卡的可能性，而且规避了数十万次sqrt函数的高昂调用开销，让程序飞快！高阶技巧 2：极其稳健的 DSU 合并作者的uni函数写的是int faa = find(a);而不是随意的fa[a]。这保证了无论在什么时机调用合并，拿到的绝对是真正的“树根”，彻底断绝了并查集结构崩塌的隐患。针对本代码的微小优化空间（代码洁癖层面）：目前代码在 Kruskal 的for循环内部，每次加边都要进行一次if(k>1)的条件判断。实际上，“目标边数”在读入N和k后就已经固定了。我们可以将n-k或n-1的计算提取到循环外部，使得核心循环的代码更加清爽。在下方的批注中已标出该优化思路。7. 完整代码(代码完全保留我的实现，请注意其中优化批注)//我们思考一下k==0的情况和k==1的情况 那就是卫星设备完全不起任何作用 //因为我们要保证每两座村庄之间都可以直接或间接地通讯 且要让d最小 //那么我们就要尽可能让最长的边尽可能短 //然后我们就想到kruskal的原理了 把所有边按照从小到大排序 //然后每次选出最短的边并检查该边的两个点是否已经属于同一个连通分量 //如果不属于 就连通 否则就继续判断下一条边 //所以我们用kruskal找出来的树 //不仅总花费最小 而且它包含的最大那条边 在所有可能的生成树中绝对是最小的 //那么当k大于等于2的时候 这k台卫星可以无视距离 //把k个互相独立的连通分量连接在一起 //所以我们的无线电不需要把所有村庄连成1棵大树（不需要加n-1条边） //无线电只需要负责把n个孤立的村庄 //连成恰好k个连通分量（即一棵包含k棵树的最小生成森林） //重点来了：在图论中从n个孤立的点 合并成k个连通分量 恰好需连接n-k条边 //因为kruskal是按边长从小到大贪心加边的 //所以 当我们成功加上第n-k条无线电边时 这片森林就刚好建成了 //而刚刚加进去的这第n-k条边 必然是整个无线电网络中最长的一条边 //它的长度 就是题目要求我们找的最小的d值 #include <iostream> #include <cmath> #include <algorithm> #include <iomanip>//对应setpresicion using namespace std; int n,k;//n座村庄 k台卫星设备 int fa[510];//fa[i]为i点集合的老大 //存每个点的坐标 struct node{ int x; int y; }no[510]; //边集数组 struct edge{ int u; int v; long long val;//存边长的平方 避免开方过程中产生精度问题 //按照边长从小到大排序 friend bool operator <(edge a,edge b){ return a.val<b.val; } }e[500010]; int idx;//存进边集数组的边数 //并查集查询并进行路径压缩 int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } //并查集合并 void uni(int a,int b){ int faa=find(a); int fab=find(b); if(faa!=fab) fa[faa]=fab; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; //存每个点的坐标 for(int i=1;i<=n;i++) cin>>no[i].x>>no[i].y; //遍历每个点i与点j之间的边 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ //省去所有重复的边 节省sort的时间 if(j>i){ idx++; e[idx].u=i; e[idx].v=j; e[idx].val=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y); } } } //把边按边长从小到大排序 sort(e+1,e+idx+1); //初始化所有点起始时集合的老大是自己 for(int i=1;i<=n;i++) fa[i]=i; int idx2=0;//idx2记录连了多少条边 //如果卫星设备数量比村庄总数多或总共只有一个村庄 输出0 直接结束程序 if(k>=n||n==1){ cout<<fixed<<setprecision(2)<<0.00; return 0; } //【优化批注】：此处可以提前计算目标边数，消去循环内的分支判定。 // 例如：int target_edges = (k <= 1) ? (n - 1) : (n - k); //接下来遍历所有边 for(int i=1;i<=idx;i++){ int a=e[i].u; int b=e[i].v; //如果a点和b点不属于一个连通分量 就连接它们 if(find(a)!=find(b)){ uni(a,b); idx2++;//连接的边数加1 } //如果k>1只需要连n-k条边即可 if(k>1){ if(idx2==n-k){ cout<<fixed<<setprecision(2)<<sqrt(e[i].val); return 0; } } //如果k==0或k==1都需要连n-1条边 即需要无线电连接所有村庄 else{ if(idx2==n-1){ cout<<fixed<<setprecision(2)<<sqrt(e[i].val); return 0; } } //【优化批注】：如果使用了 target_edges，上述逻辑可简化为： //if(idx2==target_edges) //{cout<<fixed<<setprecision(2)<<sqrt(e[i].val); return 0;} } return 0; }
【题目描述】原题来自：Waterloo University 2002北极的某区域共有 n 座村庄，每座村庄的坐标用一对整数 (x,y) 表示。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数 d，两座村庄之间的距离如果不超过 d 就可以用该型号的无线电收发机直接通讯，d 值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有 k 台卫星设备，请你编一个程序，计算出应该如何分配这 k 台卫星设备，才能使所拥有的无线电收发机的 d 值最小，并保证每两座村庄之间都可以直接或间接地通讯。例如，对于下面三座村庄：其中 |AB|=10,|BC|=20,|AC|=10√5≈22.36如果没有任何卫星设备或只有 1 台卫星设备 (k=0 或 k=1)，则满足条件的最小的 d=20，因为 A 和 B，B 和 C 可以用无线电直接通讯；而 A 和 C 可以用 B 中转实现间接通讯 (即消息从 A 传到 B，再从 B 传到 C)；如果有 2 台卫星设备 (k=2)，则可以把这两台设备分别分配给 B 和 C ，这样最小的 d 可取 10，因为 A 和 B 之间可以用无线电直接通讯；B 和 C 之间可以用卫星直接通讯；A 和 C 可以用 B 中转实现间接通讯。如果有 3 台卫星设备，则 A,B,C 两两之间都可以直接用卫星通讯，最小的 d 可取 0。【输入】第一行为由空格隔开的两个整数 n,k;第 2∼n+1 行，每行两个整数，第 i 行的 xi,yi 表示第 i 座村庄的坐标 (xi,yi)。【输出】一个实数，表示最小的 d 值，结果保留 2 位小数。【输入样例】3 2 10 10 10 0 30 0【输出样例】10.00【提示】数据范围:对于全部数据，1≤n≤500,0≤x,y≤10^4,0≤k≤100。1. 题意转换用一句话剥离题目的“北极、村庄、卫星”的包装故事：给定平面上的N个点，求将其划分为k个连通块（即构建一棵包含k棵树的最小生成森林）时，各连通块内部所有边的最大值中的最小值（最小瓶颈边）。2. 思考过程与解题思路面对这道题，第一直觉是什么？很多同学看到“通讯网络”、“连通”、“最大距离最小”，直觉可能是二分答案：二分出一个距离d，然后用 BFS/DFS 检查在这个距离下，图是否能形成个连通块。这种做法时间复杂度约为 O(N^2 log(值域))，虽然能过，但在处理浮点数二分时极易遭遇精度死循环（TLE或WA）。考点锁定：关键字：“保证直接或间接通讯”、“使最大的d最小”。这简直是把kruskal算法的“最小瓶颈生成树”特性贴在了脸上。Kruskal 算法不仅能求出边权总和最小的生成树，它找出来的树还自带神级属性：它包含的最大那条边，在所有可能让图连通的方案中，绝对是最小的！如何一步步推导到正解？没有卫星时（k=0或1）：我们需要用无线电把N个村庄连成1棵完整的大树，此时恰好需要连接N-1条边。有k台卫星时（）：卫星堪称“神级网线”，无论多远都能瞬间连通。如果我们把这k台卫星分别发给k个互相独立的连通分量，卫星就能在云端把它们免费缝合起来。核心数学映射：我们的无线电不再需要把图连成 1 棵树，只需要把N个孤立的村庄连成k个连通分量（也就是一片包含k棵树的森林）。在图论中，从N个点合并且只剩k个连通块，恰好需要成功连接N-k条边。得出结论：因为 Kruskal 是按边长从小到大贪心加边的。当我们成功加上第N-k条边时，这片森林刚刚好建成，而这最后加进去的第N-k条边，必然是网络中最长的一条边，它的长度就是题目要求的最小的d。3. 算法设计与样例推演核心逻辑与数据结构：坐标与距离计算：用结构体存点，双重循环计算任意两点间的欧几里得距离，构建完全图（跳过重复边）。边集数组edge：存储两点及距离平方（避免浮点精度问题）。并查集（DSU）：用于 Kruskal 贪心加边时的判环和合并。极简数据手玩推演：带入题目样例：N=3 座村庄，k=2 台卫星。目标边数：N-k = 3-2 = 1条边。建边与排序：AB距离为 10，BC为 20，AC约为 22.36。排序后：AB(10)BC(20)AC(22.36)。Kruskal 连线：取出最短边 AB，A 和 B 不在同一连通块，合并它们。此时成功连接了 1 条边。判定结束：已达到目标边数 1！最后加进去的边长是 10，直接输出 10.00。与样例完全吻合！4. 时空复杂度分析时间复杂度：。，建完全图会产生约条边，即。Kruskal 的瓶颈在sort，复杂度为，约执行次运算，C++ 在 1 秒内极其轻松过关。空间复杂度：。需要一个长度为M的边集数组。即便开到 500010，也仅占用十几 MB 的内存，远低于题目要求的 64MB 限制。5. 坑点与易错总结浮点数排序丢失精度（极易 WA）：如果在结构体里直接存sqrt开方后的double距离，在sort比较时极易遇到浮点数尾数精度丢失导致的排序错乱。（本题代码完美避开了这一点，后文详述）特判遗漏（极易 RE/WA）：如果卫星比村庄还多（），或者只有一个村庄（N=1），此时不需要连任何边，应当直接输出0.00并结束程序。无向图重复建边拖慢常数：建图时如果写i!=j会把边存两遍，导致sort的常数翻倍。必须用j>i来只存右上三角矩阵。6. 代码进阶与优化剖析（核心教学点）这篇题解的代码是一份几近完美的标程，其中展现了两个极高阶的竞赛编码习惯，强烈建议所有备考 CSP 的同学刻在 DNA 里：高阶技巧 1：延迟开方（降维打击精度问题）仔细看代码：long long val; //存边长的平方 避免开方过程中产生精度问题。作者极其聪明地在sort时比较的是距离的平方（绝对精度的整数），完全避免了引入double。直到程序最后一行输出答案时，才对其使用一次sqrt。这不仅避免了任何精度被卡的可能性，而且规避了数十万次sqrt函数的高昂调用开销，让程序飞快！高阶技巧 2：极其稳健的 DSU 合并作者的uni函数写的是int faa = find(a);而不是随意的fa[a]。这保证了无论在什么时机调用合并，拿到的绝对是真正的“树根”，彻底断绝了并查集结构崩塌的隐患。针对本代码的微小优化空间（代码洁癖层面）：目前代码在 Kruskal 的for循环内部，每次加边都要进行一次if(k>1)的条件判断。实际上，“目标边数”在读入N和k后就已经固定了。我们可以将n-k或n-1的计算提取到循环外部，使得核心循环的代码更加清爽。在下方的批注中已标出该优化思路。7. 完整代码(代码完全保留我的实现，请注意其中优化批注)//我们思考一下k==0的情况和k==1的情况 那就是卫星设备完全不起任何作用 //因为我们要保证每两座村庄之间都可以直接或间接地通讯 且要让d最小 //那么我们就要尽可能让最长的边尽可能短 //然后我们就想到kruskal的原理了 把所有边按照从小到大排序 //然后每次选出最短的边并检查该边的两个点是否已经属于同一个连通分量 //如果不属于 就连通 否则就继续判断下一条边 //所以我们用kruskal找出来的树 //不仅总花费最小 而且它包含的最大那条边 在所有可能的生成树中绝对是最小的 //那么当k大于等于2的时候 这k台卫星可以无视距离 //把k个互相独立的连通分量连接在一起 //所以我们的无线电不需要把所有村庄连成1棵大树（不需要加n-1条边） //无线电只需要负责把n个孤立的村庄 //连成恰好k个连通分量（即一棵包含k棵树的最小生成森林） //重点来了：在图论中从n个孤立的点 合并成k个连通分量 恰好需连接n-k条边 //因为kruskal是按边长从小到大贪心加边的 //所以 当我们成功加上第n-k条无线电边时 这片森林就刚好建成了 //而刚刚加进去的这第n-k条边 必然是整个无线电网络中最长的一条边 //它的长度 就是题目要求我们找的最小的d值 #include <iostream> #include <cmath> #include <algorithm> #include <iomanip>//对应setpresicion using namespace std; int n,k;//n座村庄 k台卫星设备 int fa[510];//fa[i]为i点集合的老大 //存每个点的坐标 struct node{ int x; int y; }no[510]; //边集数组 struct edge{ int u; int v; long long val;//存边长的平方 避免开方过程中产生精度问题 //按照边长从小到大排序 friend bool operator <(edge a,edge b){ return a.val<b.val; } }e[500010]; int idx;//存进边集数组的边数 //并查集查询并进行路径压缩 int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } //并查集合并 void uni(int a,int b){ int faa=find(a); int fab=find(b); if(faa!=fab) fa[faa]=fab; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; //存每个点的坐标 for(int i=1;i<=n;i++) cin>>no[i].x>>no[i].y; //遍历每个点i与点j之间的边 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ //省去所有重复的边 节省sort的时间 if(j>i){ idx++; e[idx].u=i; e[idx].v=j; e[idx].val=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y); } } } //把边按边长从小到大排序 sort(e+1,e+idx+1); //初始化所有点起始时集合的老大是自己 for(int i=1;i<=n;i++) fa[i]=i; int idx2=0;//idx2记录连了多少条边 //如果卫星设备数量比村庄总数多或总共只有一个村庄 输出0 直接结束程序 if(k>=n||n==1){ cout<<fixed<<setprecision(2)<<0.00; return 0; } //【优化批注】：此处可以提前计算目标边数，消去循环内的分支判定。 // 例如：int target_edges = (k <= 1) ? (n - 1) : (n - k); //接下来遍历所有边 for(int i=1;i<=idx;i++){ int a=e[i].u; int b=e[i].v; //如果a点和b点不属于一个连通分量 就连接它们 if(find(a)!=find(b)){ uni(a,b); idx2++;//连接的边数加1 } //如果k>1只需要连n-k条边即可 if(k>1){ if(idx2==n-k){ cout<<fixed<<setprecision(2)<<sqrt(e[i].val); return 0; } } //如果k==0或k==1都需要连n-1条边 即需要无线电连接所有村庄 else{ if(idx2==n-1){ cout<<fixed<<setprecision(2)<<sqrt(e[i].val); return 0; } } //【优化批注】：如果使用了 target_edges，上述逻辑可简化为： //if(idx2==target_edges) //{cout<<fixed<<setprecision(2)<<sqrt(e[i].val); return 0;} } return 0; }