【luogu P2491 [SDOI2011]消防】 题解

题目链接：https://www.luogu.org/problemnew/show/P2491

题外话：

OI一共只有三种题——会的题，不会的题，二分题。

题解：

step 1 求树的直径，把树的直径上的路径边权都置为0，这样了再求一次其他点最短路。

step 2 在树的直径上二分，具体方法是把树的直径长度用类似前缀和的思想处理后，二分左右端点舍去的距离。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 300010;
int n, dis[maxn], ans = 0x7fffffff, node, pre[maxn], path[maxn], tot, D, sta[maxn], top, s, S;
bool vis[maxn];
struct edge{
    int from, to, next, len;
}e[maxn<<2];
int cnt, head[maxn];
void add(int u, int v, int w)
{
    e[++cnt].from = u;
    e[cnt].next = head[u];
    e[cnt].len = w;
    e[cnt].to = v;
    head[u] = cnt;
}
queue<int> q;
void bfs(int s)
{
    vis[s] = 1;
    q.push(s);
    while(!q.empty())
    {
        int now = q.front(); q.pop();
        for(int i = head[now]; i != -1; i = e[i].next)
        {
            if(vis[e[i].to] == 0)
            {
                pre[e[i].to] = now;
                dis[e[i].to] = dis[now] + e[i].len;
                vis[e[i].to] = 1;
                q.push(e[i].to);
                if(dis[e[i].to] > D)
                {
                    D = dis[e[i].to];
                    node = e[i].to;
                }
            }
        }
    }
}
void SPFA(int s)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 127, sizeof(dis));
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while(!q.empty())
    {
        int now = q.front(); q.pop();
        vis[now] = 0;
        for(int i = head[now]; i != -1; i = e[i].next)
        {
            if(dis[e[i].to] > dis[now] + e[i].len)
            {
                dis[e[i].to] = dis[now] + e[i].len;
                if(!vis[e[i].to])
                {
                    q.push(e[i].to);
                    vis[e[i].to] = 1;
                }
            }
        }
    }
}
bool check(int D)
{
    int l = 1, r = top;
    while(sta[1] - sta[l+1] <= D && l <= top) l++;
    while(sta[r-1] <= D && r >= 1) r--;
    //cout<<l<<" "<<r<<endl;
    return sta[l] - sta[r] <= S;
}
int main()
{
    memset(head, -1, sizeof(head));
    int u, v, w;
    cin>>n>>S;
    for(int i = 1; i < n; i++)
    {
        scanf("%d%d%d",&u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    D = 0;
    bfs(1);
    int s = node;
    memset(vis, 0, sizeof(vis));
    dis[node] = 0;
    D = 0;
    bfs(s);
    int x = node;
    D = dis[x];
    sta[++top] = D;
    path[++tot] = x;
    
    while(x != s)
    {
        path[++tot] = pre[x];
        sta[++top] = dis[pre[x]];
        x = pre[x];
    }
    //for(int i = 1; i <= n; i++) cout<<path[i]<<" ";
    for(int i = 2; i <= tot; i++)
    {
        add(path[i-1], path[i], 0);
        add(path[i], path[i-1], 0);
    }
    SPFA(x);
    int l = 0, r = D;
    for(int i = 1; i <= n; i++) l = max(l, dis[i]);
    if(S < D)
    {
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid - 1;
            else l = mid + 1;
        }
    }
    //for(int i = 1; i <= n; i++) cout<<dis[i];
    printf("%d\n", l);
    return 0;
}

附：

sdoi居然出提高组原题（#滑稽 不过是数据扩大了1000倍

据说那个题想怎么暴怎么暴（逃