洛谷P2619《[国家集训队2]Tree I》

二月 04, 2019 3970

年轻人的第一道国家集训队
二分答案 + 最小生成树

题目描述

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

题目保证有解。

输入输出格式

输入格式

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行

每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

输出格式

一行表示所求生成树的边权和。

输入输出样例

输入样例

1
2
3
2 2 1
0 1 1 1
0 1 2 0

输出样例

1
2

说明

0:V<=10

1,2,3:V<=15

0,..,19:V<=50000,E<=100000

所有数据边权为[1,100]中的正整数。

By WJMZBMR

解题思路

年轻人的第一道国家集训队题目

如果我们不做任何处理，直接跑MST（Minimum Spanning Tree，最小生成树），结果会有三种：

  • 正好跑出 \text{Need} 条白边

  • 白边多了

  • 白边少了

第一种情况自然是最好的

剩下两种情况如何解决？

引起白边少的原因：黑边的边权相对较小，程序贪心地选择了更多的黑边

引起白边多的原因：白边的边权相对较小，程序贪心地选择了更多的白边

那么如果我们给白边相应地减去/加上一些边权，不就可以达成目标了？

考虑二分答案。

我们二分一个 add 表示我们当前要给白边加上 add 来达成目标

边界分别是边权最小值（-100）和边权最大值（100）

由于题面保证有答案，所以直接输出 ans - add \times \text{Need}
即可，其中 ans 为（加上边权后）最小生成树的权值和

Check(mid) 怎么写？

我们将所有白边的边权加上 add （即 mid ），跑一遍最小生成树，判断一下拿到的白色边数量是否大于等于要求的数量，如果是就更新一下左边界并记当前的 mid 为 tans ，否则就更新一下右边界

注意不要忘了把边权减回来

（不要在意 tans 是什么意思）

刚才我们不是记录了一下 tans 吗，这个 tans 就相当于是一个正确的、能选出正好 \text{Need} 条白边的 add 值，再将所有白边的边权都加上这个 tans ，跑一遍最小生成树即可

答案不要忘了减去加上的边权（也就是 \text{Need} \times tans ）

那么最后的答案就是 \text{Kruskal()} - \text{Need} \times tans

代码实现

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <algorithm>
#include <iostream>
#include <cstdio>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

#define WHITE 0
#define BLACK 1

using std::cin;
using std::cout;
using std::endl;
using std::max;

const int MAXV = 50000 + 10;
const int MAXE = 100000 + 10;
const int MAXW = 100;

struct Edge {
    int prev, next, weight, add;
    bool color;
    // 1 -> black, 0 -> white
    
    Edge() { prev = next = weight = color = add = 0; }
    
    bool operator < (const Edge &that) const {
        if (weight == that.weight) return color < that.color;
        return weight < that.weight;
    }
} edge[MAXE << 1];

int V, E, Need, cnt, ans;

int U[MAXV << 1];

int Find(int x) {
    if (U[x] == x) return U[x];
    return U[x] = Find(U[x]);
}

bool Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return false;
    U[x] = y;
    return true;
}

int Kruskal() {
    int whiteEdge = 0;
    for (int i = 1; i <= V; ++i) U[i] = i;
    std::sort(edge + 1, edge + 1 + E);
    int tot = 0;
    ans = 0;
    for (int i = 1; i <= E; ++i) {
        if (Union(edge[i].prev, edge[i].next)) 
            ans += edge[i].weight, ++tot, whiteEdge += (edge[i].color == WHITE);
        if (tot == V - 1) break;
    }
    return whiteEdge;
}

bool Check(int add) {
    for (int i = 1; i <= E; ++i) {
        if (edge[i].color == WHITE) edge[i].weight += add;
    }
    bool Ans = (Kruskal() >= Need);
    for (int i = 1; i <= E; ++i) {
        if (edge[i].color == WHITE) edge[i].weight -= add;
    }
    return Ans;
}

int main() {
    IMPROVE_IO();
    cin >> V >> E >> Need;
    for (int i = 1; i <= E; ++i) {
    	cin >> edge[i].prev >> edge[i].next >> edge[i].weight >> edge[i].color;
    	++edge[i].prev;
        ++edge[i].next;
    }
    int l = -MAXW, r = MAXW;
    int Run = 0;
    while (l <= r) {
        int mid = ((l + r) >> 1);
        if (Check(mid)) {
            l = mid + 1;
            Run = mid;
        } else {
            r = mid - 1;
        }
    }
    Check(Run);
    cout << ans - Need * Run << endl;
    return 0;
}