带权二分 学习笔记

发表于 | 分类于 | | + s

模板及讲解

什么时候用带权二分

它的作用就是题目给了一个选物品的限制条件，要求刚好选$m$个，让你最大化（最小化）权值，然后其特点就是当选的物品越多的时候权值越大（越小）。

算法分析

我们先不考虑物品限制条件，假定我们要最大化权值。然后其中我们二分一个$C$，表示选一次物品的附加权值，如果我们$C$越大，我们选的物品个数越多，权值越大，于是当选的物品个数大于$m$时，减小$C$，否则增大$C$，最后计算答案的时候去掉$C$值的影响即可。

例题：Bzoj 2654

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

https://loj.ac/article/872
二分$x \in [-\text{MaxC}, \text{MaxC}]$, 每条边权加上$x$, 做最小生成树，权值相同优先选，判断选的白边数量与$K$的关系

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, m, K, f[100000 + 5];

    struct edge {
        int u, v, w, c;
        bool operator < (const edge &rhs) const {return w == rhs.w ? c < rhs.c : w < rhs.w;}
    } ed[100000 + 5];

    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}

    pair<int, LL > chk(int x) {
        for (int i = 1; i <= m; ++i) if (ed[i].c == 0) ed[i].w += x;
        sort(ed + 1, ed + 1 + m);

        for (int i = 1; i <= n; ++i) f[i] = i;
        int cnt = 0;
        LL sum = 0;
        for (int i = 1; i <= m; ++i) {
            int a = find(ed[i].u), b = find(ed[i].v);
            if (a != b) {
                f[a] = b;
                if (ed[i].c == 0) ++cnt; 
                sum += ed[i].w;
            }
        }
        for (int i = 1; i <= m; ++i) if (ed[i].c == 0) ed[i].w -= x;
        return make_pair(cnt, sum);
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> m >> K;
        for (int i = 1; i <= m; ++i) scanf("%d%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w, &ed[i].c), ++ed[i].u, ++ed[i].v;

        int l = -110, r = 110;
        LL ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            pair<int, LL > tmp = chk(mid);
            int d = tmp.first;
            LL sum = tmp.second;
            if (d >= K) l = mid + 1, ans = sum - 1ll * K * mid;
            else r = mid - 1;
        }
        printf("%lld\n", ans);

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
4 5 2
0 1 5 1
0 3 4 1
0 2 5 1
0 1 100 0
1 3 4 0
*/
------ 本文结束 ------