「HNOI2006」公路修建问题 - 二分答案 + 最小生成树

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

OI island 是一个非常漂亮的岛屿，自开发以来，到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association 组织成立了，旨在建立 OI island 的交通系统。

OI island 有 \(n\) 个旅游景点，不妨将它们从 \(1\) 到 \(n\) 标号。现在，OIER Association 需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。

OIER Association 打算修 \(n-1\) 条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率， OIER Association 希望在这 \(n-1\) 条公路之中，至少有 \(k\) 条 \((0 \le k \le n-1)\) 一级公路。OIER Association 也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。

而你的任务就是，在给定一些可能修建的公路的情况下，选择 \(n-1\) 条公路，满足上面的条件。

解题思路

这道题求的是满足条件的最大公路花费的最小值。显然我们可以二分答案最长边的权值。

而对于本题中对一级公路的限制，我们可以在最长边权值限制下尽量多地选择一级公路构成生成树。在一级公路选完后再选二级公路。

最后通过调整二分，找出其中一级公路满足条件且所选边足够构成一棵树地最大边权的最小值即为答案。

本题同时要求输出方案，可在求生成树的时候同时把所选边存下来即可。

代码演示

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
99
100
#include <cstdio>
#include <algorithm>

const int MAXN = 1e4;
const int MAXM = 2e4;
const int MAXC = 3e4;

struct Edge {
    int a, b;
    int c1, c2;
    int id;

    bool operator<(const Edge &other) const {
        return c1 < other.c1;
    }
} E[MAXM + 1];

struct UFS {
    int f[MAXN + 1];

    void init(int n) {
        for (int i = 1; i <= n; i++) f[i] = i;
    }

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

    void merge(int x, int y) {
        f[find(x)] = find(y);
    }
} ufs;

int n, k, m;
std::pair<int, int> id[MAXN];

inline bool solve(int limit) {
    static std::pair<int, int> ids[MAXN];
    ufs.init(n);
    int cnt = 0;

    for (int i = 1; i <= m - 1; i++) {
        Edge &e = E[i];
        if (e.c1 > limit) break;
        if (ufs.find(e.a) == ufs.find(e.b)) continue;

        ufs.merge(e.a, e.b);
        ids[++cnt] = std::make_pair(e.id, 1);
    }
    if (cnt < k) return false;

    for (int i = 1; i <= m - 1; i++) {
        if (cnt == n - 1) {
            for (int i = 1; i <= n - 1; i++) id[i] = ids[i];
            return true;
        }

        Edge &e = E[i];
        if (e.c2 > limit) continue;
        if (ufs.find(e.a) == ufs.find(e.b)) continue;

        ufs.merge(e.a, e.b);
        ids[++cnt] = std::make_pair(e.id, 2);
    }

    if (cnt == n - 1) {
        for (int i = 1; i <= n - 1; i++) id[i] = ids[i];
        return true;
    }

    return false;
}

int main() {
    scanf("%d %d %d", &n, &k, &m);

    int l = MAXC, r = 1;
    for (int i = 1; i <= m - 1; i++) {
        scanf("%d %d %d %d", &E[i].a, &E[i].b, &E[i].c1, &E[i].c2);
        E[i].id = i;
        l = std::min(l, std::min(E[i].c1, E[i].c2));
        r = std::max(r, std::max(E[i].c1, E[i].c2));
    }
    std::sort(E + 1, E + m);

    while (l < r) {
        int mid = (l + r) >> 1;

        if (solve(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", l);
    std::sort(id + 1, id + n - 1);
    for (int i = 1; i <= n - 1; i++) {
        printf("%d %d\n", id[i].first, id[i].second);
    }

    return 0;
}