[HNOI 2006] 公路修建问题

题目大意

给定一个 nn 个定点、mm 条边的图,每条边有 w1w1w2w2 两个权值(可视作是两条边),求至少有 kk 条边选择第一权值的生成树中,最大边权的最小值。

1n10,0001 \leqslant n \leqslant 10,000

1m20,0001 \leqslant m \leqslant 20,000

题目链接

【HNOI 2006】公路修建问题 - Luogu 2323

题解

用类似 Kruskal 的方法,先选出 kk 条第一权值的边,再求最小生成树。

代码

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
#include <cstdio>
#include <algorithm>
const int MAXN = 10005;
const int MAXM = 20005;
struct Edge {
int u, v, w, type;
Edge() {}
Edge(int u, int v, int w, int type) : u(u), v(v), w(w), type(type) {}
bool operator<(const Edge &another) const {
return w < another.w;
}
} E[MAXM << 1];
struct UnionFindSet {
int fa[MAXN];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int p = find(x), q = find(y);
if (p == q) return;
fa[q] = p;
}
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i;
}
} ufs;
int main() {
int n, k, m;
scanf("%d %d %d", &n, &k, &m);
m--;
int cnt = 0;
for (int i = 0; i < m; i++) {
int u, v, w1, w2;
scanf("%d %d %d %d", &u, &v, &w1, &w2);
E[cnt++] = Edge(u, v, w1, 1);
E[cnt++] = Edge(u, v, w2, 2);
}
m = cnt;
std::sort(E, E + m);
int ans = 0;
ufs.init(n);
for (int i = 0; i < m; i++) {
if (E[i].type == 1 && ufs.find(E[i].u) != ufs.find(E[i].v)) {
ufs.merge(E[i].u, E[i].v);
ans = std::max(ans, E[i].w);
n--;
if (!--k) break;
}
}
for (int i = 0; i < m; i++) {
if (ufs.find(E[i].u) != ufs.find(E[i].v)) {
ufs.merge(E[i].u, E[i].v);
ans = std::max(ans, E[i].w);
if (--n == 1) break;
}
}
printf("%d\n", ans);
return 0;
}