[BZOJ2282]消防

Description

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

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

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

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

Input

输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。

Output

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

Sample Input

【样例输入1】
5 2
1 2 5
2 3 2
2 4 4
2 5 3

【样例输入2】
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

Sample Output

【样例输出1】

5
【样例输出2】

HINT

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

Source

stage 2 day1

首先我们应该想到这条路径一定在树的直径上。这里给出证明：

设直径的长度为d，那么直径外的边长度一定小于等于d/2（否则该路径会与直径的一部分构成一条比直径还长的路径）

若该路径不在直径上，则直径的最远点到该路径的距离至少为d/2

而如果在直径上，一定存在一段路径使得树上所有点的距离到它不超过d/2

所以选在直径上一定是优的，而且在符合题目要求的情况下越长越好。

那么如果我们确定里直径，我们可以O(n)求出直径上每个点到最远点的距离，然后左右指针扫直径，单调队列维护区间最小值即可。

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 using namespace std;

 deque<int>q;

 struct point

 {

     int to;

     int next;

     int dis;

 }e[];

 int n,x,y,z,res=,maxn,s,t,num,ss;

 int d[],head[],f[],pre[];

 bool vis[];

 void add(int from,int to,int dis)

 {

     e[++num].next=head[from];

     e[num].to=to;

     e[num].dis=dis;

     head[from]=num;

 }

 void dfs(int x)

 {

     vis[x]=true;

     for(int i=head[x];i!=;i=e[i].next)

     {

         int to=e[i].to;

         if(!vis[to])

         {

             d[to]=d[x]+e[i].dis;

             dfs(to);

         }

     }

 }

 void dfs1(int x)

 {

     vis[x]=true;

     for(int i=head[x];i!=;i=e[i].next)

     {

         int to=e[i].to;

         if(!vis[to])

         {

             pre[to]=x;

             d[to]=d[x]+e[i].dis;

             dfs1(to);

         }

     }

 }

 void find(int x)

 {

     vis[x]=true;

     for(int i=head[x];i!=;i=e[i].next)

     {

         int to=e[i].to;

         if(!vis[to])

         {

             find(to);

             d[x]=max(d[x],d[to]+e[i].dis);

         }

     }

 }

 void getf()

 {

     int slr=;

     for(int i=t;i!=;i=pre[i])

     {

         f[i]=slr;

         for(int j=head[i];j!=;j=e[j].next)

         {

             int to=e[j].to;

             if(pre[i]==to)

             {

                 slr+=e[j].dis;

                 break;

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&ss);

     for(int i=;i<=n-;i++)

     {

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z);

         add(y,x,z);

     }

     dfs();

     for(int i=;i<=n;i++)

     {

         if(d[i]>maxn)

         {

             maxn=d[i];

             s=i;

         }

     }

     memset(vis,false,sizeof(vis));

     memset(d,,sizeof(d));

     dfs1(s);

     maxn=;

     for(int i=;i<=n;i++)

         if(d[i]>maxn)

         {

             maxn=d[i];

             t=i;

         }

     memset(vis,false,sizeof(vis));

     memset(d,,sizeof(d));

     for(int i=t;i!=;i=pre[i])

         vis[i]=true;

     for(int i=t;i!=;i=pre[i])

         find(i);

     getf();

     int r=t,l=pre[t];

     q.push_front(l);

     if(d[l]<d[r])

         q.push_back(r);

     while()

     {

         if(pre[l]!=&&f[pre[l]]-f[r]<=ss)

         {

             l=pre[l];

             int ans=max(f[r],maxn-f[l]);

             q.push_front(l);

             while(d[q.back()]<d[l])

                 q.pop_back();

             ans=max(ans,d[q.back()]);

             res=min(res,ans);

         }

         else if(l!=r)

         {

             if(q.back()==r)

                 q.pop_back();

             r=pre[r];

             int ans=max(f[r],maxn-f[l]);

             ans=max(ans,d[q.back()]);

             res=min(res,ans);

         }

         else if(l==r&&pre[l])

         {

             while(!q.empty())

                 q.pop_back();

             l=pre[l];

             r=l;

             q.push_front(l);

             int ans=max(f[r],maxn-f[l]);

             ans=max(ans,d[q.back()]);

             res=min(res,ans);

         }

         else

             break;

     }

     printf("%d",res);

     return ;

 }

这道题综合了许多算法，也有一定的思维难度，是一道不可多得好题

巴特西