给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有 need 条白色边的生成树。题目保证有解

链接🔗
「2012 集训队互测」 Tree

题解

二分 + 最小生成树
二分一个权值,将每条白边都加上这个权值,然后跑最小生成树,如果使用的白边少了,则说明权值加大了,反之则说明权值加少了

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e5 + 10;
int n, m, need, f[maxd * 5], sum;
struct node {
    int a, b, c, col, d;
    bool operator<(const node& other) const {
        if (d == other.d)
            return col < other.col;
        return d < other.d;
    }
} e[maxd];
void init() {
    for (int i = 0; i <= n; i++) f[i] = i;
    sum = 0;
}
int gf(int x) {
    if (f[x] == x)
        return x;
    return f[x] = gf(f[x]);
}
int solve(int x) {
    init();
    int ans = 0, cnt = 0;
    for (int i = 1; i <= m; i++) e[i].d = e[i].c + (1 ^ e[i].col) * x;
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; i++) {
        int a = gf(e[i].a), b = gf(e[i].b);
        if (a == b)
            continue;
        ans += 1 ^ e[i].col;
        f[a] = b;
        sum += e[i].d;
        cnt++;
        if (cnt + 1 == n)
            return ans;
    }
    return ans;
}
int main() {
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    scanf("%d %d %d", &n, &m, &need);
    for (int i = 1; i <= m; i++) scanf("%d %d %d %d", &e[i].a, &e[i].b, &e[i].c, &e[i].col);
    int l = -100, r = 100, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (solve(mid) >= need) {
            // printf("%d %d\n",sum,mid);
            ans = sum - need * mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    printf("%d", ans);
    return 0;
}