[洛谷P2491] [SDOI2011]消防

时间:2022-05-25 18:42:22

洛谷题目链接:[SDOI2011]消防

题目描述

某个国家有n个城市,这n个城市中任意两个都连通且有唯一一条路径,每条连通两个城市的道路的长度为zi(zi<=1000)。

这个国家的人对火焰有超越宇宙的热情,所以这个国家最兴旺的行业是消防业。由于*对国民的热情忍无可忍(大量的消防经费开销)可是却又无可奈何(总统竞选的国民支持率),所以只能想尽方法提高消防能力。

现在这个国家的经费足以在一条边长度和不超过s的路径(两端都是城市)上建立消防枢纽,为了尽量提高枢纽的利用率,要求其他所有城市到这条路径的距离的最大值最小。

你受命监管这个项目,你当然需要知道应该把枢纽建立在什么位置上。

输入输出格式

输入格式:

输入包含n行:

第1行,两个正整数n和s,中间用一个空格隔开。其中n为城市的个数,s为路径长度的上界。设结点编号以此为1,2,……,n。

从第2行到第n行,每行给出3个用空格隔开的正整数,依次表示每一条边的两个端点编号和长度。例如,“2 4 7”表示连接结点2与4的边的长度为7。

输出格式:

输出包含一个非负整数,即所有城市到选择的路径的最大值,当然这个最大值必须是所有方案中最小的。

输入输出样例

输入样例#1:

5 2
1 2 5
2 3 2
2 4 4
2 5 3

输出样例#1:
5

输入样例#2:

8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

输出样例#2:

5

说明

【数据规模和约定】

对于20%的数据,n<=300。

对于50%的数据,n<=3000。

对于100%的数据,n<=300000,边长小等于1000。

一句话题意: 给出一颗树,在树上选一条长度小于等于\(s\)的一条简单路径,要求出其他所有点到选定路径上的点的距离的最小值.

题解: 首先我们知道,每一个点到树上最远的另一个点,那另一个点一定在直径上.所以我们可以直接枚举直径上的点,然后在找直径上的点到其他点的距离最大是多少.

先来想一下暴力要怎么做(暴力分可以参照树网的核, 其实是同一道题).

我们可以先处理出树上的一条直径,然后再暴力枚举直径上的两个端点,再求出其他点到直径上的点最大的距离是多少.显然这样是\(O(n^3)\)的.

然后观察一下题目的性质,显然在直径上取的距离越大越优,因为如果选取的长度变长,到其他点的距离是一定不会减小的,而只有可能缩小,所以可以枚举一个起点,然后直接取\(k\)的长度,再\(O(k)\)验证,复杂度\(O(n*k)\).

但是这样还是不够我们通过这道题.然后我们发现,答案是具有单调性的.感性理解一下,如果最长距离越大,也就越容易满足,反之则反.所以我们可以二分最大距离,然后\(O(n)\)枚举起点验证,总复杂度\(O(nlogn)\).

其实这题还有更好的算法,我们可以发现,在直径上取最大值的时候是通过移动左右指针来实现的,也就是说我们可以用单调队列来优化这个过程.这样复杂度就降到了\(O(n)\).这里我是使用的这种方法.

#include<cstdio>
#include<iostream>
using namespace std;
const int N = 300000+5;

int n, s, last[N], ecnt = 0;
int dep[N], mx[N], fa[N], len = 0, ans = 0, f[N], L, R, vis[N], pre[N], cnt = 0, node[N], q[N], dist[N], pos[N];

struct edge{
    int to, nex, w;
}e[N*2];

void add(int x, int y, int z){
    e[++ecnt].to = y, e[ecnt].w = z, e[ecnt].nex = last[x], last[x] = ecnt;
}

void dfs(int x, int las, int deep){
    dep[x] = deep, fa[x] = las;
    for(int to, i=last[x];i;i=e[i].nex){
    to = e[i].to; if(to == las) continue;
    dfs(to, x, deep+1);
    if(len < f[x]+f[to]+e[i].w) len = f[x]+f[to]+e[i].w, L = pre[x], R = pre[to];
    if(f[x] < f[to]+e[i].w) f[x] = f[to]+e[i].w, pre[x] = pre[to];
    }
}

int get_dis(int x, int f){
    int maxx = 0;
    for(int to, i=last[x];i;i=e[i].nex){
    to = e[i].to;
    if(vis[to] || to == f) continue;
    maxx = max(maxx, get_dis(to, x)+e[i].w);
    }
    return maxx;
}

void dfs2(int x, int lca){
    if(x == lca){ node[++cnt] = x; return; }
    dfs2(fa[x], lca), node[++cnt] = x;
}

void init(){
    for(int i=2;i<=cnt;i++)
    for(int j=last[node[i]];j;j=e[j].nex)
        if(e[j].to == node[i-1]) dist[node[i]] = dist[node[i-1]]+e[j].w;
}

void tag(int x, int y){
    int lca, a = x, b = y;
    if(dep[a] < dep[b]) swap(a, b);
    while(dep[a] > dep[b]) vis[a] = 1, a = fa[a];
    if(a == b) vis[a] = 1, lca = a;
    else {
    while(a != b) vis[a] = vis[b] = 1, a = fa[a], b = fa[b];
    vis[a] = 1, lca = a;
    }
    while(x != lca) node[++cnt] = x, x = fa[x];
    dfs2(y, lca), init();
    for(int i=1;i<=cnt;i++) mx[node[i]] = max(mx[node[i]], get_dis(node[i], -1));
}

int solve(){
    int h = 1, t = 0, h1 = 1, t1 = 0, res = 1e9;
    for(int i=1;i<=cnt;i++){
    while(h <= t && mx[node[q[t]]] < mx[node[i]]) t--; q[++t] = i, pos[++t1] = i;
    while(h <= t && h1 <= t1 && dist[node[pos[t1]]]-dist[node[pos[h1]]] > s)
    q[h] == pos[h1] ? h1++, h++ : h1++;
    res = min(res, max(mx[node[q[h]]], max(dist[node[pos[h1]]], dist[node[cnt]]-dist[node[pos[t1]]])));
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    int x, y, z; cin >> n >> s;
    for(int i=1;i<=n;i++) pre[i] = i;
    for(int i=1;i<n;i++) cin >> x >> y >> z, add(x, y, z), add(y, x, z);
    dfs(1, -1, 1), tag(L, R);
    cout << solve() << endl;
    return 0;
}