[SDOI2011]消防（树的直径+二分||单调队列）

题目描述

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

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

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

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

输入输出格式

输入格式：

输入包含n行：

第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。

从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

输入样例#2：复制

输出样例#2：复制

说明

【数据规模和约定】

对于20%的数据，n<=300。

对于50%的数据，n<=3000。

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

最重要的一点就是路径一定全都在树的直径上，至于证明就自行百度吧嘿嘿：

确定直径的两个端点 l 和 r ，维护直径上的每个点到达的最远的点的距离（不包括直径上的点),要么二分最大值，把两个端点向里缩mid，判断距离两个端点之间的点（不包括端点，因为到一个点最远的点一定是直径的一个端点）最远的距离是否大于mid，和两个端点之间的距离是否小于题目的条件s；

或者是维护单调不增的队列，路径越长越好，维护头尾的距离不超过s，取ans=min(ans,max(q[头],max( dis[头],dis[端点】-dis[尾}))

只有二分的码qwq：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 const int N=2000001;
 8 struct node{
 9     int to,nex,v;
10 }e[N<<1];
11 int dep[N],dis[N],vis[N],ff[N],son[N];
12 int maxn,s,t,n,k,l,r;
13 int num,head[N];
14 
15 void add(int from,int to,int v){
16     num++;
17     e[num].to=to;
18     e[num].v=v;
19     e[num].nex=head[from];
20     head[from]=num;
21 }
22 
23 int read(){
24     int x=0,w=1;char ch=getchar();
25     while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
26     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
27     return x*w;
28 }
29 
30 void dfs(int x,int fa){
31     for(int i=head[x];i;i=e[i].nex){
32         int v=e[i].to;if(v==fa)continue;ff[v]=x;
33         dis[v]=dis[x]+e[i].v;dfs(v,x);
34     }
35 }
36 
37 void dfs2(int x){
38     dep[x]=0;int maxx=0;
39     for(int i=head[x];i;i=e[i].nex){
40         int v=e[i].to;if(v==ff[x]||vis[v])continue;
41         dfs2(v);maxx=max(maxx,e[i].v+dep[v]);
42     }
43     dep[x]=maxx;
44 }
45 
46 bool judge(int mid){
47     int sum=0,sum1=0,sum2=0,ll=s,rr=t;
48     while(sum1-dis[ll]+dis[son[ll]]<=mid&&ll!=rr&&ll){
49         sum1+=dis[son[ll]]-dis[ll];ll=son[ll];
50     }
51     while(sum2+dis[rr]-dis[ff[rr]]<=mid&&rr!=ll&&rr){
52         sum2+=dis[rr]-dis[ff[rr]];rr=ff[rr];
53     }
54     //if(dis[rr]<dis[ll])return false;
55     while(rr!=ll)
56     {sum+=dis[rr]-dis[ff[rr]];
57     if(dep[rr]>mid)return false;
58     rr=ff[rr];
59     }
60     if(dep[ll]>mid)return false;
61     if(sum>k)return false;
62     return true;
63 }
64 
65 int main(){
66     n=read();k=read();
67     for(int i=1;i<n;i++){
68         int x=read(),y=read(),z=read();
69         add(x,y,z);add(y,x,z);r+=z;
70     }
71     dfs(1,0);for(int i=1;i<=n;i++){if(dis[i]>maxn)maxn=dis[i],s=i;ff[i]=dis[i]=0;}
72     dfs(s,0);maxn=0;
73     for(int i=1;i<=n;i++){if(dis[i]>maxn)maxn=dis[i],t=i;}
74     int now=t;
75     while(now){
76         vis[now]=1;son[ff[now]]=now;now=ff[now];
77     }
78     now=t;
79     while(now!=ff[s]){
80         dfs2(now);
81         now=ff[now];
82     }
83     while(r>l){
84         int mid=(l+r)>>1;
85         if(judge(mid))r=mid;
86         else l=mid+1;
87     }
88     printf("%d
",l);
89     return 0;
90 }

[SDOI2011]消防（树的直径+二分||单调队列）

题目描述

输入输出格式

输入输出样例

说明

相关推荐