P16237 [蓝桥杯 2026 省 B] 应急布线

题目链接P16237 [蓝桥杯 2026 省 B] 应急布线 - 洛谷这道题卡了我比较久主要是第一次学习了并查集这种算法以及这道题的处理方式一、问题化简把每台计算机看作点每条仍能工作的网线看作无向边。则通过残存网线或跳线直接或间接连通即图上的连通。设当前图由 C个连通块组成。每条应急跳线连接两台计算机即一条新边。目标一用最少的边使全图连通。目标二在边数最少的前提下最小化单个点上关联的跳线条数的最大值。二、目标一最少跳线数C个连通块要并成一片每加一条边最多使连通块数减一因此至少需要 C−1条边。另一方面把 C个连通块依次串成一条链相邻两块之间连一条跳线恰好用 C−1条即可全部连通。故第一问答案为ans1C−1特别地当 C1 时答案均为 0。三、目标二均衡分摊关键是把计数对象从连通块换成线头。共需 C−1 条跳线每条跳线有两个端点因此共有 2(C−1)个线头线头必须落在具体的计算机上。由于每个连通块内部已经连通块内任意一台计算机都可以作为接线点。因此全部 NN 台计算机都是可用插口。于是问题转化为把 K2(C−1)个线头分配到 N 台计算机上最小化单台承担数的最大值。设单台上限为 t则 NN 台最多容纳 Nt个线头。要容纳全部线头须取满足该式的最小整数需要注意这个值只是下界只有当它确实可以通过某种布线方案取到时才是答案。可以构造证明它可达将各连通块按内部可用机器数排布成一棵树机器数多的块置于内部、只有一台机器的块置于叶位置再把块所需的线头按其内部机器轮流分配即不会超过该上限。代码#include bits/stdc.h using namespace std; int n, m; vectorint fa; // 并查集fa[x] 表示 x 的父结点 // 查找 x 所在集合的代表元同时进行路径压缩 int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } // 合并 x、y 所在的两个集合 void unite(int a, int b) { a find(a); b find(b); if (a b) return; // 已属同一集合无需合并 fa[a] b; // 将一个代表元挂到另一个代表元之下 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; // 1. 并查集初始化每个点单独成为一个集合 fa.resize(n 1); for (int i 1; i n; i) fa[i] i; // 2. 读入残存网线并合并 for (int i 0; i m; i) { int u, v; cin u v; unite(u, v); } // 3. 统计连通块个数代表元即满足 fa[i] i 的点 int comp 0; for (int i 1; i n; i) if (fa[i] i) comp; // 4. 已全连通无需布线 if (comp 1) { cout 0 0\n; return 0; } // 5. 第一问C 个连通块至少需要 C-1 条边 long long ans1 comp - 1; // 6. 第二问每条边两个端点共 2*(C-1) 个线头分摊到 n 台机器上 // 对 n 向上取整得到单台承担数的下界且该下界可达到 long long heads 2 * ans1; long long ans2 (heads n - 1) / n; // 向上取整的整数写法 cout ans1 ans2 \n; return 0; }