题解 CF73D 【FreeDiv】

pythoner713 · 2021-09-22 13:53:57 · 题解

假设我们在第一步中已经随便连了一些边，那么怎么判断是否可以通过操作二使图联通呢？

经过操作一后，设当前图中的联通块大小分别是 a_1,a_2,\dots,a_d。注意到操作二可以等价于以下表述：对于第 i 个连通块，最多向外连出 \min(a_i,k) 条边。而要想令这 d 个连通块联通，至少还需要 d-1 条边。因此操作二能使当前图联通，当且仅当：

乘以 2 是因为一条边会被统计两次。

那么现在正解就呼之欲出了，第一步的连边无非是为了合并原图连通块，达到减小 d 的目的，但是合并后出的新连通块大小要尽量不超过 k，不然会让不等式左侧减小。因此我们可以用小根堆维护当前所有连通块大小，每次选取最小的两个连通块合并，直到上述不等式成立即可。

#include<bits/stdc++.h>
#define nb 1000010
using namespace std;

int ans, d, n, m, k, E, fa[nb], size[nb];
priority_queue<int, vector<int>, greater<int>> q;

int find(int x){
    while(x != fa[x])
        x = fa[x] = fa[fa[x]];
    return x;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 0, u, v; i < m; i++)
        cin >> u >> v, fa[find(u)] = find(v);
    for(int i = 1; i <= n; i++) size[find(i)]++;
    for(int i = 1; i <= n; i++){
        if(find(i) == i) q.push(size[i]), d++;
        E += min(k, size[i]);
    }
    while(1){
        if(E >= 2 * d - 2){
            cout << ans;
            return 0;
        }
        ans++;
        int u, v;
        u = q.top(), q.pop();
        v = q.top(), q.pop();
        d--, E -= min(u, k) + min(v, k);
        E += min(k, u + v);
        q.push(u + v);
        // E 即为不等式左侧的值
        // 每次贪心地取两个最小的连通块合并
        // 一旦有 E >= 2(d - 1) 说明可以进入操作二, 输出答案
    }
    return 0;
}