[SDOI2011]消防 (树的直径,尺取法)

题目链接

Solution

同 \(NOIP2007\) 树网的核 .

令 \(dist_u\) 为以 \(u\) 为根节点的子树中与 \(u\) 的最大距离.
\(~~~~dis_u\) 为 \(u\) 到直径中没有包括区间的一端的距离.
\(~~~~s\) 为直径.
题意很明确,要求直径上的一段区间使得 \(Max(dist_u(u\epsilon s),dis_u)\) 最小.
考虑 \(O(n)\) ,直接在直径上尺取就好了...
考虑 \(O(nlogn)\) ,直接二分+枚举起点就好了.
然而数据过水,直接打的 \(O(n^2)\) ,结果\(A\)了.

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1008;
struct sj{
int to,next,w;
}a[maxn*2];
int head[maxn],size;
int n,s,x,y,w;
int read()
{
    int f=1,w=0; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}
    return f*w;
}
void add(int x,int y,int w)
{
    a[++size].to=y;
    a[size].next=head[x];
    head[x]=size;a[size].w=w;
}

int last,num,now,cnt,v[maxn],bcnt;
int ans[maxn],maxx,road[maxn];
int dist[maxn],b[maxn],ansb[maxn];
int sum[maxn];
void dfs(int x)
{
    v[x]=1;
    road[++cnt]=x;
    for(int i=head[x];i;i=a[i].next)
    {
         int tt=a[i].to;
         if(!v[tt])
         {
            now+=a[i].w;
            b[++bcnt]=a[i].w;
            dfs(tt); cnt--;bcnt--;
            now-=a[i].w;
         }
    }
    if(now>maxx)
    {
        num=cnt; last=x; maxx=now;
        for(int i=1;i<=cnt;i++)
        ans[i]=road[i],ansb[i]=b[i];
    }
}

void getdist(int x)
{
    v[x]=1;
    maxx=max(maxx,now);
    for(int i=head[x];i;i=a[i].next)
    {
        int tt=a[i].to;
        if(!v[tt])
        {
            now+=a[i].w;
            getdist(tt);
            now-=a[i].w;
        }
    }
}

int main()
{
    n=read(); s=read();
    for(int i=1;i<n;i++)
    {
        x=read(); y=read(); w=read();
        add(x,y,w); add(y,x,w);
    }
    dfs(1);
    memset(v,0,sizeof(v));
    maxx=0; cnt=0; now=0;
    dfs(last);
    memset(v,0,sizeof(v));
    for(int i=1;i<=num;i++)v[ans[i]]=1;
    for(int i=2;i<=num;i++)sum[i]=sum[i-1]+ansb[i-1];
    for(int i=1;i<=num;i++)
    {maxx=0,getdist(ans[i]),dist[i]=maxx;}
    
    int q[maxn]={0},kk=192608173;
    int h=1,t=0;
    for(int i=1;i<=num;i++)
    {
        int fuck=-1;
        for(int j=i;j<=num;j++)
        {
            fuck=max(fuck,dist[j]);
            if(sum[j]-sum[i]>s)break;
            kk=min(kk,max(max(sum[i],sum[num]-sum[j]),fuck));
        }
    }
    cout<<kk<<endl;
}

[SDOI2011]消防 (树的直径,尺取法)

原文：https://www.cnblogs.com/Kv-Stalin/p/9506545.html