DDOSvoid's Blog

Luogu P2619 [国家集训队]Tree I

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P2619

Solution

令 $f_k$ 表示有 $k$ 条白边的最小生成树的权值，$(i,f_i)$ 组成的点是下凸，这一点就不证明了

我们考虑带权二分，如果使用小数二分的话，不会出现权值相同的白边和黑边，所以一定能二分到对应的斜率 $k$

所以我们直接上小数二分是没有任何细节的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
#define maxn 50010
#define maxm 100010
using namespace std;

const double eps = 1e-7;

int n, m, k;

struct Edge {
    int fr, to, col;
    double w, _w; 

    friend bool operator < (const Edge &u, const Edge &v) {
        return u.w < v.w;
    } 
} e[maxm];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

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

pair<int, double> check(double x) {
    for (int i = 1; i <= m; ++i)
        if (!e[i].col) e[i].w = e[i]._w - x;
    sort(e + 1, e + m + 1); init_fa(n);
    pair<int, double> ans = { 0, 0 };
    for (int i = 1; i <= m; ++i) { 
        int u = e[i].fr, v = e[i].to, col = e[i].col, fu, fv; double w = e[i].w;
        if ((fu = find(u)) == (fv = find(v))) continue;
        ans.first += !col; ans.second += w;
        fa[fv] = fu;
    }
    return ans;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k; 
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].fr >> e[i].to >> e[i].w >> e[i].col;
        ++e[i].fr; ++e[i].to; e[i]._w = e[i].w;
    }
    double l = -100, r = 100, mid, ans;
    while (r - l > eps) {
        mid = (l + r) / 2; 
        pair<int, double> res = check(mid);
        if (res.first >= k) ans = res.second + k * mid, r = mid;
        else l = mid;
    } cout << (int) (ans + 0.5) << "\n";
    return 0;
}

好像整数二分，然后在排序的时候优先排白边好像也行的样子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
#define maxn 50010
#define maxm 100010
using namespace std;

int n, m, k;

struct Edge {
    int fr, to, w, col, _w;

    friend bool operator < (const Edge &u, const Edge &v) {
        if (u.w != v.w) return u.w < v.w;
        return u.col < v.col; 
    } 
} e[maxm];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

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

pair<int, int> check(int x) {
    for (int i = 1; i <= m; ++i)
        if (!e[i].col) e[i].w = e[i]._w - x;
    sort(e + 1, e + m + 1); init_fa(n);
    pair<int, int> ans = { 0, 0 };
    for (int i = 1; i <= m; ++i) { 
        int u = e[i].fr, v = e[i].to, w = e[i].w, col = e[i].col, fu, fv;
        if ((fu = find(u)) == (fv = find(v))) continue;
        ans.first += !col; ans.second += w;
        fa[fv] = fu;
    }
    return ans;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k; 
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].fr >> e[i].to >> e[i].w >> e[i].col;
        ++e[i].fr; ++e[i].to; e[i]._w = e[i].w;
    }
    int l = -100, r = 100, mid, ans;
    while (l <= r) {
        mid = l + r >> 1;
        pair<int, int> res = check(mid);
        if (res.first >= k) ans = res.second + k * mid, r = mid - 1;
        else l = mid + 1; 
    } cout << ans << "\n";
    return 0;
}