洛谷P2491 [SDOI2011] 消防题解

题目链接：P2491 [SDOI2011] 消防

题意：某个国家有 $n$ 个城市，这 $n$ 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 $z_i$ 。

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

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

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

看到这是一棵树，而且还要求路径的最大值

很容易想到这个枢纽要建在直径上

当 $s$ 大于等于直径时显然成立

考虑 $s$ 小于直径的情况，枢纽全部建在直径上仍是最优解

以下为证明：

假设只有一个枢纽结点（在直径上），我们以它为中心扩展出一条路径

离这个点最远的结点一定在直径上，而且是直径的端点

此时的最大值就是这条路径的长度

那么如果扩展枢纽结点，只有在直径上扩展，才可能更新这个最大值

因此枢纽一定在直径上

证毕。

于是，我们可以想到个暴力做法

先找出直径，然后枚举每一个直径上的点 $u$ 作为枢纽的起点进行扩展

找到满足条件且最远的 $v$ ，并对每组 $(u,v)$ 计算出直径的两个端点到枢纽的最大距离

再计算出非直径的结点到枢纽的最大距离即可，时间复杂度 $O(n^2)$

注：因为两端到枢纽的距离不一定是最大值，可以参考下图

那么怎么优化呢

注意到选择的枢纽长度随结点数量的增加单调递增

因此我们可以考虑使用尺取法

这样，算法的流程就变成了

找出直径
对于每个极大枢纽，统计两端到其距离的最大值的最小值
统计非直径结点到枢纽距离的最大值

时间复杂度 $O(n)$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(3e5+15)
struct Edge
{
    int u,v,w,next;
}e[N<<1];
int n,s,ans=INF;
int pos=1,head[N],x,y,dis[N],pre[N],pd[N];
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void dfs(int u,int f)
{
    pre[u]=f;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f||pd[v])continue;
        dis[v]=dis[u]+e[i].w;
        dfs(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> s;
    for(int i=1,u,v,w; i<n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    dis[1]=1;dfs(1,0);
    x=max_element(dis+1,dis+1+n)-dis;
    dis[x]=0;dfs(x,0);
    y=max_element(dis+1,dis+1+n)-dis;
    for(int i=y,j=y; i; i=pre[i])
    {
        pd[i]=1;
        while(dis[j]-dis[i]>s)j=pre[j];
        ans=min(ans,max(dis[i],dis[y]-dis[j]));
    }
    for(int i=y; i; i=pre[i])
    {
        dis[i]=0;
        dfs(i,pre[i]);
    }
    for(int i=1; i<=n; i++)
        ans=max(ans,dis[i]);
    cout << ans << endl;
    return 0;
}