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

· · 题解

题意理解

给定一张 N 个节点、M 条边的无向图。

需要求出：

  1. 至少添加多少条边（记作 K）。
  2. 在添加 K 条边使得图连通的所有方案中，新边带来的节点度数的最大值最小值。

注意：原图中已有的边不计入新边度数。

最少加边数

原有 M 条边将图划分成了若干个连通分量。设连通分量数量为 c。要把它们连成一整棵树（或连通图），最少需要 c-1 条边。因此 K = c - 1。

最小化最大度数

设每个块有 s_i 台机，容量上限 A\cdot s_i，总容量 A\cdot N\ge 2K，足够装下所有端点。

故答案为 K 和 \lceil \frac{2K}{N}\rceil。

实现

用并查集统计连通分量个数 c，则 K = c-1。

时间复杂度：并查集近似 O(N+M)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int fa[N];
int Find(int x){
    if(fa[x]==x) return x;
    return fa[x]=Find(fa[x]);
}
void Union(int x,int y){
    fa[Find(x)]=Find(y);
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        Union(a,b);
    }
    int cnt=-1;
    for(int i=1;i<=n;i++) cnt+=(Find(i)==i);
    cout<<cnt<<" "<<((2*cnt+n-1)/n);
}