题意描述
洛谷链接
LibreOJ 链接
C 城将要举办一系列的赛车比赛。在比赛前，需要在城内修建 \(m\) 条赛道。
C 城一共有 \(n\)
个路口，这些路口编号为 \(1,2, \cdots ,
n\)，有 \(n − 1\)
条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第 \(i\) 条道路连接的两个路口编号为 \(a_i\) 和 \(b_i\)，该道路的长度为 \(l_i\)。借助这 \(n
− 1\) 条道路，从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 \(e_1, e_2,
\cdots , e_k\)，满足可以从某个路口出发，依次经过道路 \(e_1, e_2, \cdots ,
e_k\)（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的
\(m\)
条赛道中长度最小的赛道长度最大（即 \(m\) 条赛道中最短赛道的长度尽可能大）。
解题思路
本题求的是最小赛道的最大值，可二分答案。而难点则在二分答案的判定上。
设二分时赛道长度为 \(\text{limit}\)，我们需要考虑一颗子树上形成的长度满足条件的赛道最多有多少个。对于这个问题，我们可以贪心解决。
设对于 \(v\) 为树上一节点，\(u\) 为 \(v\) 的父节点。设以 \(u\)、\(v\)
为根的子树分别最多有 \(f_u\)、\(f_v\) 个赛道，\(u\) 可利用 \(v\) 的最长路径为 \(g_v\)。
对于 \(u \stackrel{w}{\longrightarrow}
v\)，我们有两种情况：
- \(w + g_v \ge
\text{limit}\)，此时我们可直接将该边与 \(v\) 中剩余的路径连起来形成一条新的赛道。即
\(f_u = f_v + 1\)；
- \(w + g_v \ge
\text{limit}\)，此时我们无法形成一条完整的赛道。此时我们需要将这个路径保存以便后续使用。
对于节点 \(u\)
保存的路径，我们有两种情况：
- 由于保存的路径端点均为 \(u\)，我们可将两条路径连在一起形成一条赛道；
- 将路径保存至 \(g_u\)，以便 \(u\) 的父节点使用。
我们可以证明：我们尽量满足情况 \(1\)，对于无法满足情况 \(1\) 的路径中取最长路径满足情况 \(2\)。这种方法不劣。因为对于 \(u\) 的父节点，我们至多只能形成一条利用
\(u\) 的赛道。而对于对 \(u\) 的父节点有用的路径，使用情况 \(1\) 和情况 \(2\) 对答案的贡献是等价的。对于对 \(u\) 的父节点无用的路径，使用情况 \(1\) 显然更优。
对于路径的保存，我们用 multiset 保存，用
lower_bound 查询可连接成赛道的路径即可。时间复杂度 \(O(n \log n \log L)\)，其中 \(L\) 为边权和。
代码演示
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
| #include <cstdio>
#include <iostream>
#include <vector>
#include <set>
const int MAXN = 5e4;
struct Node {
std::vector<struct Edge> e;
std::multiset<int> s;
} N[MAXN + 1];
struct Edge {
Node *s, *t;
int w;
Edge(Node *s, Node *t, int w) : s(s), t(t), w(w) {}
};
int n, m;
int cnt = 0;
inline void addEdge(int s, int t, int w) {
N[s].e.push_back(Edge(&N[s], &N[t], w));
N[t].e.push_back(Edge(&N[t], &N[s], w));
}
int dfs(Node *v, int limit, Node *f = NULL) {
v->s.clear();
for (Edge *e = &v->e.front(); e && e <= &v->e.back(); e++) {
if (e->t == f) continue;
int res = dfs(e->t, limit, v);
if (res + e->w >= limit) cnt++;
else v->s.insert(res + e->w);
}
int max = 0;
while (!v->s.empty()) {
if (v->s.size() == 1) return std::max(max, *v->s.begin());
std::multiset<int>::iterator it = v->s.lower_bound(limit - *v->s.begin());
if (it == v->s.begin() && v->s.count(*it) == 1) it++;
if (it == v->s.end()) {
max = std::max(max, *v->s.begin());
v->s.erase(v->s.begin());
} else {
cnt++;
v->s.erase(it);
v->s.erase(v->s.begin());
}
}
return max;
}
int main() {
scanf("%d %d", &n, &m);
int max = 0;
for (int i = 1; i <= n - 1; i++) {
int a, b, l;
scanf("%d %d %d", &a, &b, &l);
addEdge(a, b, l);
max += l;
}
int l = 0, r = max;
while (l < r) {
int mid = (l + r + 1) / 2;
cnt = 0;
dfs(&N[1], mid);
if (cnt >= m) l = mid;
else r = mid - 1;
}
printf("%d\n", l);
return 0;
}
|