【SDOI2011】消防

题目链接：https://www.luogu.com.cn/problem/P2491

题目大意：给定一棵带有 \(n\) 个点的树 , 求出在这棵树的直径中的不超过长度 \(s\) 的路径, 其中的每个点到其他点的距离的最大值最小

solution

一道看似很奇怪的辣鸡题 , 其实就是树网的核的加强版

题目挺难看懂的 , 但经过仔细地思考以后 , 若令 \(d[i]\) 等于从点 \(i\) 到 其它点的最大距离 , 原题就可以简化为求:

\[min_{r \leq len}\left\{max_{l \leq i \leq r}\left\{d[i]\right\}(dist(l, r) \leq s)\right\}(其中 len 表示直径上点的个数)\]

令 \(pre[i]\) 表示从直径的一个端点到第 \(i\) 个点的距离 , 由直径的最长性 , 可得 \(d[i] = pre[i]\) , 从而原式可变为:

\[max_{l \leq i \leq r}\left\{max\left\{pre[len] - pre[r] , pre[l]\right\}\right\}(dist(l, r) \leq s)\]

但这个式子仍有一个问题 , 当这条路径上中间有一些点出现了直径的分支时 , 实际上从另一条直径的端点走到这些点的距离会更大 , 于是我们可以令 \(dis[i]\) 表示点 \(i\) 不经过直径上的点到其他点的最大距离 , 这个式子又可以转化为:

\[max_{l \leq i \leq r}\left\{max\left\{pre[len] - pre[r] , pre[l] , dis[i]\right\}\right\}(dist(l, r) \leq s)\]

令 \(dist[k] = max_{i \leq k}\left\{dis[i]\right\}\) , 则原式还可以转化为

\[max_{l \leq i \leq r}\left\{dist[r], max\left\{pre[len] - pre[r] , pre[l] \right\}\right\}(dist(l, r) \leq s)\]

此时 \(dist[r]\) 是一个定值 , \(max\left\{pre[len] - pre[r] , pre[l] \right\}(dist(l, r) \leq s)\) 也可以用类似于单调队列的方法快速求出 , 于是这道题就可以咕咕咕地解决了

时间复杂度 : \(O(n)\)

code

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &FF) {
    int RR = 1; FF = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
    for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
    FF *= RR;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 1e6 + 10;
int n, s, res, id, vis[N], lt[N], lw[N], d[N];
int now, fst[N], nxt[N], num[N], wi[N], yi[N], pre[N], si;
void add(int u, int v, int w) {
    nxt[++now] = fst[u], fst[u] = now, num[now] = v, wi[now] = w;
    nxt[++now] = fst[v], fst[v] = now, num[now] = u, wi[now] = w;
}
int get_longest(int xi) {
    res = id = 0;
    queue<pair<int, int> > qi;
    for(int i = 1; i <= n; i++) lt[i] = i, vis[i] = 0;
    qi.push(make_pair(xi, 0));
    while(!qi.empty()) {
        pair<int, int> pi = qi.front(); qi.pop();
        vis[pi.first] = 1;
        if(pi.second > res) res = pi.second, id = pi.first;
        for(int i = fst[pi.first]; i; i = nxt[i])
            if(!vis[num[i]]) {
                lt[num[i]] = pi.first, lw[num[i]] = wi[i];
                qi.push(make_pair(num[i], pi.second + wi[i]));
            }
    }
    return id;  
}
int dfs(int xi) {
    vis[xi] = 1; int ans = 0;
    for(int i = fst[xi]; i; i = nxt[i])
        if(!vis[num[i]]) ans = max(ans, wi[i] + dfs(num[i]));
    return ans;
}
void get_len() {
    int li = get_longest(1), ri = get_longest(li);
    for(int i = 1; i <= n; i++) vis[i] = 0;
    yi[++si] = ri, pre[si] = 0, vis[ri] = 1;
    while(lt[ri] != ri) {
        yi[++si] = lt[ri], pre[si] = pre[si - 1] + lw[ri];
        ri = lt[ri], vis[ri] = 1;
    }
    for(int i = 1; i <= si; i++) d[i] = dfs(yi[i]);
}
int main() {
    //file("");
    int u, v, w;
    read(n), read(s);
    for(int i = 1; i < n; i++)
        read(u), read(v), read(w), add(u, v, w);
    get_len(); int st = 1, ans = INT_MAX, tmax = 0;
    if(s >= res) {
        ans = 0;
        for(int i = 1; i <= si; i++)
            ans = max(ans, d[i]);
        cout << ans << endl;
        return 0;
    }
    for(int i = 1; i <= si; i++) {
        tmax = max(tmax, d[i]);
        while(st <= i && pre[i] - pre[st] > s) st++;
        ans = min(ans, max(tmax, max(pre[st], res - pre[i])));
    }
    cout << ans << endl;
    return 0;
}

【SDOI2011】消防

原文：https://www.cnblogs.com/magicduck/p/12253345.html