题解：P17484 月兔通信网络

csy_12 · 2026-09-25 19:31:27 · 题解

题意

给你一个无向图，最多添加 n-1 条边，使图连通，并让最终图中两点之间最短路的最大值尽可能小，输出最优加边方案。

思路

分两种情况讨论。

原图缺 \frac{n(n-1)}{2}-m 条边才能成为完全图。

情况一：

原图缺的边比较少，\frac{n(n-1)}{2}-m \le n-1。直接把所有缺的边全部加上，这样最终直接变成完全图。完全图中任意两个点之间都有边，所以最大通信难度就是 1。

情况二：

缺至少 n 条边，不可能成为完成图，即 \frac{n(n-1)}{2}-m > n-1。我们就把 1 号点和所有不与它相连的点连起来。任意两个点 u,v 之间都可以通过 u \rightarrow 1 \rightarrow v 到达，所以最大通信难度是 2。

代码

int T,n,m,f[M];
vector<int> mp[M];
set<pair<int,int>> e;
vector<pair<int,int>> ans;
signed main()
{
    T=rd();
    while(T--){
        n=rd(),m=rd();
        rep(i,1,n) f[i]=0,mp[i].clear();
        e.clear();
        ans.clear();
        rep(i,1,m){
            int u=rd(),v=rd();
            if(u>v) swap(u,v);
            mp[u].push_back(v);
            mp[v].push_back(u);
            e.insert({u,v});
        }
        if(n*(n-1)/2-m<n){
            rep(i,1,n) rep(j,i+1,n)
                if(!e.count({i,j})) ans.push_back({i,j});
        }
        else{
            for(int v:mp[1]) f[v]=1;
            rep(i,2,n) if(!f[i]) ans.push_back({1,i});
        }
        printf("%lld\n",ans.size());
        for(auto[u,v]:ans) printf("%lld %lld\n",u,v);
    }
}