洛谷P1099 树网的核

\(\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;
} 

洛谷P1099 树网的核

原文：https://www.cnblogs.com/Miraclys/p/12408766.html