- \(\Large\textbf{Description: } \large{给你一个无根树和一个非负整数 \ text{s}, 求直径上的一段长度不超过 \ text{s} 的路径 F, 使树上结点到 F 距离最大值的最小值.(5 \leq n \leq 300, 0 \leq s \leq 1000)\\}\)
- \(\Large\textbf{Solution: } \large{一道特别经典的题目, 解法很多, 值得反复推敲.\\ 介绍一种解法. 我们可以先 \ text{dfs} 找出树的直径, 并在 \ text{dfs} 过程中维护 \ text{dis} 与 \ text{fa}.\\ 我们可以在直径上借助尺取法, 遍历一遍直径顺便维护 \ text{ans}.\\ 注意, 当 \ text{s} 大于直径的时候, 我们的最大值就要 \ text{dfs} 一下, 求出其余点到直径上任意一点的距离的最大值即可.}\)
- \(\Large\textbf{Code: }\)
- #include <cstdio>
- #include <algorithm>
- #define LL long long
- #define gc() getchar()
- #define rep(i, a, b) for(int i = (a); i <= (b); ++i)
- #define _rep(i, a, b) for(int i = (a); i <= (b); ++i)
- using namespace std;
- const int N = 305;
- const int Inf = 0xfffffff;
- int n, cnt, s, cur, Max, ans = Inf, head[N], vis[N], dis[N], f[N];
- struct Edge {
- int to, next, val;
- }e[N <<1];
- inline int read() {
- char ch = gc();
- int ans = 0;
- while (ch> '9' || ch <'0') ch = gc();
- while (ch>= '0' && ch <= '9') ans = (ans <<1) + (ans << 3) + ch - '0', ch = gc();
- return ans;
- }
- inline void add(int x, int y, int w) {
- e[++cnt].to = y;
- e[cnt].next = head[x];
- e[cnt].val = w;
- head[x] = cnt;
- }
- inline void dfs1(int x, int fa) {
- f[x] = fa;
- for (int i = head[x]; i ; i = e[i].next) {
- int u = e[i].to;
- if (u == fa) continue;
- dis[u] = dis[x] + e[i].val;
- if (dis[u]> Max) Max = dis[u], cur = u;
- dfs1(u, x);
- }
- }
- inline void dfs2(int x, int fa) {
- for (int i = head[x]; i ; i = e[i].next) {
- int u = e[i].to;
- if (u == fa) continue;
- if (!vis[u]) dis[u] = dis[x] + e[i].val, ans = max(ans, dis[u]);
- dfs2(u, x);
- }
- }
- int main() {
- n = read(), s = read();
- int x, y, w;
- rep(i, 2, n) x = read(), y = read(), w = read(), add(x, y, w), add(y, x, w);
- dfs1(1, 0);
- int l = cur;
- rep(i, 1, n) dis[i] = 0;
- Max = 0, dfs1(l, 0);
- int r = cur;
- for (int i = r, j = r; i; i = f[i]) {
- vis[i] = 1;
- while (dis[j] - dis[i]> s) j = f[j];
- Max = max(dis[i], dis[r] - dis[j]);
- ans = min(ans, Max);
- }
- rep(i, 1, n) dis[i] = 0;
- dfs2(r, 0);
- printf("%d\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3446693.html