「国家集训队」Tree I

题目大意：给定一张 $n$ 个点 $m$ 条边的无向图，每条边为黑色或白色，求一棵恰好有 $k$ 条白边的最小生成树。$n \leq 5 \times 10^4, m \leq 10^5$

「APIO 2008 免费道路」的加强版，由求任意一棵生成树变成求权值最小的生成树。

如果我们想尽可能的多的白边我们要将白边权值加一个很大的负数，如果我们想尽可能的少的白边我们要将白边权值加一个很大的正数。这个是满足二分的性质的。因此可以二分所有白边所加的权值，每次求最小生成树。

注意一个细节，如果二分过程中给白边加上 $mid$，得到的白边数比 $k$ 大；给白边加上 $mid+1$，得到的白边比 $k$ 小。如果出现这种情况，一定是有很多相等的白边和黑边，因为数据保证合法。所以我们可以把一些白边替换成黑边。因此统计答案时，不能把所有白边都减去 $mid$，而是只减去 $k \times mid$。

#include <cstdio>
#include <algorithm>
 
const int N = 100005;
 
struct Edge {
    int u, v, w, f;
    bool operator < (const Edge &rhs) const {
        if (w == rhs.w) return f < rhs.f;
        return w < rhs.w;
    }
} e[N];
 
int fa[N], n, m, k, sum, ans;
 
int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
bool check(int v) {
    int cnt = 0; sum = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) if (!e[i].f) e[i].w += v;
    std::sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; ++i) {
        int fx = find(e[i].u), fy = find(e[i].v);
        if (fx == fy) continue;
        fa[fx] = fy, sum += e[i].w, cnt += e[i].f == 0;
    }
    for (int i = 1; i <= m; ++i) if (!e[i].f) e[i].w -= v;
    return cnt >= k;
}
 
int main() {
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; ++i)
        e[i].u = read() + 1, e[i].v = read() + 1, e[i].w = read(), e[i].f = read();
    int l = -100, r = 100;
    while (l <= r) {
        int mid = l + (r - l >> 1);
        if (check(mid)) l = mid + 1, ans = sum - k * mid; //注意这里不能取min, 要直接赋值
        else r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(m \log m)$