BZOJ2282 SDOI2011 消防 BFS+单调队列

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

题意:给定一棵树,求树上一条长度不大于S的路径,使得树上所有点到该路径的最大距离最小。

题解:

首先,所求路径一定在树的直径上,否则我们总可以用树的直径来扩展出更大的最大距离。

设fi为i为路径左端点时,直径的右端点到i的距离;gi为i为路径右端点时,直径的左端点到i的距离;hi为i的与直径没有交集的子树中,到i的最远距离。对于一个确定的路径ab,显然我们有\[Dist = \max (\max ({f_l},{g_r}),\max \{ {h_i}\} ),i \in [l,r]\]

然后用双端队列来维护后面h的最大值即可

——————————————————————————————

这个题到这里就算做完了,但是有个问题……我不会求树的直径QAQ

所以这里说一下怎么求树的直径:首先随便确定一个根Root,BFS出其他所有节点到Root的距离d[i],找出s使得d[s]最大,令Root=s,再跑一遍BFS,然后找出t使得d[t]最大,那么s到t的路径就是这棵树的直径。证明可以看这里

BZOJ2282 SDOI2011 消防 BFS+单调队列BZOJ2282 SDOI2011 消防 BFS+单调队列
#include <cstdio>
#include
<climits>
#include
<cstring>
#include
<cstdlib>
#include
<iostream>
#include
<algorithm>
#include
<queue>
using namespace std;

const int MAXN=300000+2;
struct Hash{
int u,w;
Hash
*Next;
Hash(){}
Hash(
int _u,int _w,Hash *_Next):u(_u),w(_w),Next(_Next){}
}
*Tab[MAXN],Mem[2*MAXN];
int N,S,F=1,T,f[MAXN],g[MAXN],h[MAXN],Fa[MAXN],Flag[MAXN],Link[MAXN],C,Tmp[MAXN],Mark[MAXN],dq[MAXN],L,R,Ans=INT_MAX,cnt;
queue
<int> q;

void Insert(int u,int v,int w){ Tab[u]=&(Mem[cnt++]=Hash(v,w,Tab[u]));}

int BFS(int s,int t){
int Len=-1;
q.push(s),g[s]
=0,Fa[s]=s,Flag[s]=t;

int x;
while(!q.empty()){
x
=q.front(),q.pop();
for(Hash *p=Tab[x];p;p=p->Next)
if(Flag[p->u]!=t){
g[p
->u]=g[x]+p->w,Flag[p->u]=t,Fa[p->u]=x;
q.push(p
->u),Len=max(Len,g[p->u]);
}
}
return Len;
}

int main(){
cin
>> N >> S;
for(int i=1,u,v,w;i<N;i++){
scanf(
"%d %d %d",&u,&v,&w);
Insert(u,v,w),Insert(v,u,w);
}

BFS(F,
1);
for(int i=1;i<=N;i++)
if(g[i]>g[F]) F=i;
BFS(F,
2);
for(int i=1;i<=N;i++)
if(g[i]>g[T]) T=i;
Link[
++C]=T;
do{
T
=Fa[T],Link[++C]=T,Flag[T]=3;
}
while(T!=F);

for(int i=1;i<=C;i++) f[i]=g[Link[1]]-g[Link[i]];
for(int i=1;i<=C;i++) Tmp[i]=g[Link[i]];
for(int i=1;i<=C;i++) h[i]=BFS(Link[i],3);
for(int i=1;i<C;i++) g[i]=Tmp[i];
g[C]
=0;

for(int l=1,r=0;l<=C;l++){
while(r<C && f[r+1]-f[l]<=S){
r
++;
while(L<=R && dq[R]<h[r]) R--;
dq[
++R]=h[r],Mark[R]=r;
}
Ans
=min(Ans,max(max(f[l],g[r]),dq[L]));
if(Mark[L]<=l) L++;
}
cout
<< Ans << endl;

return 0;
}
View Code