CF73D FreeDiv 题解

题目链接：FreeDiv

题意：

你要执行以下两步操作：

1. 在图中任意连边

2. 在第一步操作后得到一张新图，在新图中继续连边。

   要求每个点只能在这步中连一条边，每个新图中的连通块只能连 \(k\) 条边

要求在这两步操作后图是连通的，求第一步中最少要连多少边

数据范围：

\(1 \le n,k \le 10^6,~0 \le m \le 10^6\)

显然这个第一步操作实际上是由第二步的决策决定的。

注意到要使得图连通，我们可以用两个连通块连一条边这样的方式合并

考虑把原图的连通块看作一个点，设有 \(d\) 个连通块。

由于让这 \(d\) 个点连通至少需要 \(d-1\) 条边，则当且仅当 \[ \sum_{i=1}^d \min \left(a_i, k\right) \geq 2(d-1) \] 时，我们可以通过操作二完成合并。

而第一个操作实际上在减少 \(d\) ，同时左侧如果加的边不好可能会让左侧减小。

考虑用小根堆维护每个连通块的大小，每次取最小的两个连通块合并，直到上述不等式成立即可。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

struct DSU
{
    int f[N], sz[N];
    void init(int n) { rep(i, 1, n) { f[i] = i, sz[i] = 1; } }
    int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    void merge(int u, int v)
    {
        int x = find(u), y = find(v);
        if(sz[x] > sz[y]) swap(x, y);
        f[x] = y; sz[y] += sz[x];
    }
}D;
int n, m, k, d, cnt, ans, sz[N];
priority_queue<int, vector<int>, greater<int>> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k; D.init(n); 
    rep(i, 1, m) { int u, v; cin >> u >> v, D.merge(u, v); }
    rep(i, 1, n) ++sz[D.find(i)];
    rep(i, 1, n)
    {
        if(D.find(i) == i) { q.push(sz[i]), ++d; }
        cnt += min(k, sz[i]);
    }
    while(cnt < 2 * d - 2)
    {
        int u = q.top(); q.pop();
        int v = q.top(); q.pop();
        ++ans; --d; cnt -= min(u, k) + min(v, k);
        cnt += min(k, u + v); q.push(u + v);
    }
    cout << ans << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/4iy7migr