[HNOI2006] 公路修建问题

题意

有 $n$ 个景点，候选公路一共若干条。

每条候选公路有两种修法：

一级公路，花费 $c1$
二级公路，花费 $c2$

并且 $c2 <= c1$ 。

你要选出 $n-1$ 条公路把所有景点连起来，并且：

其中至少有 $k$ 条是一级公路
所选公路里，花费最大的那一条尽量小

最后输出这个最小可能的“最大花费”，以及一组对应方案。

思路

先看一个小数据暴力：

cpp

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149// brute.cpp：小数据枚举所有生成树，再枚举一级/二级公路分配。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXM = 20;
const int INF = 1e9;

struct Edge {
    int id;
    int u, v;
    int c1, c2;
} edges[MAXM];

struct AnswerEdge {
    int id;
    int level;
};

int n, need_level1, m_input;
int edge_cnt;
int picked[MAXM];
int fa[MAXN];
int best_cost = INF;
vector<AnswerEdge> best_answer;

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

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

bool unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) {
        return false;
    }
    fa[x] = y;
    return true;
}

void update_answer(const vector<AnswerEdge> &answer, int cost) {
    vector<AnswerEdge> cur = answer;
    sort(cur.begin(), cur.end(), [](const AnswerEdge &a, const AnswerEdge &b) {
        return a.id < b.id;
    });

    if (cost < best_cost) {
        best_cost = cost;
        best_answer = cur;
    }
}

void enumerate_types(int pos, int cnt_level1, int cur_cost, vector<AnswerEdge> &answer) {
    if (pos > n - 1) {
        if (cnt_level1 >= need_level1) {
            update_answer(answer, cur_cost);
        }
        return;
    }

    Edge &e = edges[picked[pos]];

    answer.push_back({e.id, 1});
    enumerate_types(pos + 1, cnt_level1 + 1, max(cur_cost, e.c1), answer);
    answer.pop_back();

    answer.push_back({e.id, 2});
    enumerate_types(pos + 1, cnt_level1, max(cur_cost, e.c2), answer);
    answer.pop_back();
}

void check_tree(int picked_cnt) {
    if (picked_cnt != n - 1) {
        return;
    }

    init_dsu();
    for (int i = 1; i <= picked_cnt; i++) {
        Edge &e = edges[picked[i]];
        if (!unite(e.u, e.v)) {
            return;
        }
    }

    int root = find_root(1);
    for (int i = 2; i <= n; i++) {
        if (find_root(i) != root) {
            return;
        }
    }

    vector<AnswerEdge> answer;
    enumerate_types(1, 0, 0, answer);
}

void dfs(int pos, int picked_cnt) {
    if (picked_cnt > n - 1) {
        return;
    }
    if (pos > edge_cnt) {
        check_tree(picked_cnt);
        return;
    }
    if (picked_cnt + (edge_cnt - pos + 1) < n - 1) {
        return;
    }

    picked[picked_cnt + 1] = pos;
    dfs(pos + 1, picked_cnt + 1);
    dfs(pos + 1, picked_cnt);
}

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

    cin >> n >> need_level1 >> m_input;

    edge_cnt = 0;
    int a, b, c1, c2;
    while (cin >> a >> b >> c1 >> c2) {
        edge_cnt++;
        edges[edge_cnt] = {edge_cnt, a, b, c1, c2};
    }

    dfs(1, 0);

    if (best_answer.empty()) {
        cout << -1 << '\n';
        return 0;
    }

    cout << best_cost << '\n';
    for (AnswerEdge e : best_answer) {
        cout << e.id << ' ' << e.level << '\n';
    }

    return 0;
}

暴力直接枚举生成树，再枚举每条边修一级还是二级：

只保留至少有 $k$ 条一级公路的方案
计算这组方案里的最大边权
取最小值

这个思路按定义完全正确，但显然只适合很小数据。

关键在于：目标不是最小化总花费，而是最小化所选边中的最大花费。

这类题的标准做法就是二分答案。

设我们猜测答案是 $T$ ，问题变成：

是否存在一棵生成树，使得每条被选中的边费用都不超过 $T$ ，并且至少有 $k$ 条一级公路？

对一条边 (u,v,c1,c2) 来说：

如果 $c2 <= T$ ，那么它至少可以按二级公路使用
如果 $c1 <= T$ ，那么它还可以按一级公路使用

于是把边分成两类：

可用边： $c2 <= T$
可作为一级公路的边： $c1 <= T$

先看“能不能连成树”：

只要所有可用边能把全图连通，就至少存在一棵生成树所有边费用都不超过 $T$

再看“最多能有多少条一级公路”：

把所有 $c1 <= T$ 的边单独拿出来看，它们会形成若干个连通块
在这些边内部，一棵极大生成森林最多能选出 $n - cnt$ 条一级公路，其中 cnt 是这些点集的连通块个数

这是上界，而且可达到：

先把所有一级可行边尽量选成一片森林
再用普通可用边把这些块接起来

所以对于给定的 $T$ ，可行条件就是：

$c2 <= T$ 的边能连通全图
$c1 <= T$ 的边最多能提供的一级公路数量不少于 $k$

这两个条件都能用并查集线性检查，因此整体可以二分 $T$ 。

二分出最小可行 $T$ 后，再构造一组答案：

先用所有 $c1 <= T$ 的边做一片极大森林，并把这些边都当作一级公路
再用 $c2 <= T$ 的边把整张图补成生成树，这些边作为二级公路

因为极大森林已经保证一级公路数量尽量多，所以只要 $T$ 可行，这样构造出来的一定满足“至少 $k$ 条一级公路”。

代码

cpp

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXM = 20005;

struct Edge {
    int id;
    int u, v;
    int c1, c2;
} edges[MAXM];

struct AnswerEdge {
    int id;
    int level;
};

int n, need_level1, m_input;
int edge_cnt;
int fa1[MAXN], fa2[MAXN], fa_build[MAXN];

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

int find_root(int fa[], int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa, fa[x]);
    return fa[x];
}

bool unite(int fa[], int x, int y) {
    x = find_root(fa, x);
    y = find_root(fa, y);
    if (x == y) {
        return false;
    }
    fa[x] = y;
    return true;
}

bool feasible(int limit_cost) {
    init_dsu(fa1);
    init_dsu(fa2);

    int comp_all = n;
    int comp_level1 = n;

    for (int i = 1; i <= edge_cnt; i++) {
        if (edges[i].c2 <= limit_cost && unite(fa1, edges[i].u, edges[i].v)) {
            comp_all--;
        }
        if (edges[i].c1 <= limit_cost && unite(fa2, edges[i].u, edges[i].v)) {
            comp_level1--;
        }
    }

    int max_level1_edges = n - comp_level1;
    return comp_all == 1 && max_level1_edges >= need_level1;
}

vector<AnswerEdge> build_answer(int limit_cost) {
    vector<AnswerEdge> answer;
    init_dsu(fa_build);

    // 先尽量加入所有能加入的一级公路，得到一级公路子图的极大生成森林。
    for (int i = 1; i <= edge_cnt; i++) {
        if (edges[i].c1 > limit_cost) {
            continue;
        }
        if (unite(fa_build, edges[i].u, edges[i].v)) {
            answer.push_back({edges[i].id, 1});
        }
    }

    // 再用二级可行的边把各个一级公路连通块接起来。
    for (int i = 1; i <= edge_cnt; i++) {
        if ((int)answer.size() == n - 1) {
            break;
        }
        if (edges[i].c2 > limit_cost) {
            continue;
        }
        if (unite(fa_build, edges[i].u, edges[i].v)) {
            answer.push_back({edges[i].id, 2});
        }
    }

    sort(answer.begin(), answer.end(), [](const AnswerEdge &a, const AnswerEdge &b) {
        return a.id < b.id;
    });
    return answer;
}

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

    cin >> n >> need_level1 >> m_input;

    edge_cnt = 0;
    vector<int> values;
    int a, b, c1, c2;
    while (cin >> a >> b >> c1 >> c2) {
        edge_cnt++;
        edges[edge_cnt] = {edge_cnt, a, b, c1, c2};
        values.push_back(c1);
        values.push_back(c2);
    }

    if (edge_cnt == 0) {
        cout << -1 << '\n';
        return 0;
    }

    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    if (!feasible(values.back())) {
        cout << -1 << '\n';
        return 0;
    }

    int left = 0;
    int right = (int)values.size() - 1;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (feasible(values[mid])) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    int best = values[left];
    vector<AnswerEdge> answer = build_answer(best);

    cout << best << '\n';
    for (AnswerEdge e : answer) {
        cout << e.id << ' ' << e.level << '\n';
    }

    return 0;
}

复杂度

设实际读到的候选公路数为 $m$ 。

每次二分检查：

扫一遍边做两个并查集，复杂度 $O(m α(n))$

二分次数是 $O(log V)$ ，其中 $V$ 是费用值域或不同费用个数。

总复杂度可以写成：

$O(m log m + m α(n) log V)$

空间复杂度 $O(n + m)$ 。

总结

这题最关键的一步，是把“至少 $k$ 条一级公路”转化成一个图论上界：在所有一级可行边构成的子图里，最多能放多少条一级公路。这样一来，原题就从一个看起来很难的双重限制，降成了一个标准的二分可行性问题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[HNOI2006] 公路修建问题

目录

题意

思路

代码

复杂度

总结

一图流解析