首页 > 代码库 > bzoj 1767: [Ceoi2009]harbingers
bzoj 1767: [Ceoi2009]harbingers
Description
给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向capital(1号结点)，每到一个城市他可以有两种选择： 1.继续走到下个城市 2.让这个城市的邮递员替他出发。 每个邮递员出发需要一个准备时间W[I]，他们的速度是V[I]，表示走一公里需要多少分钟。 现在要你求出每个城市的邮递员到capital的最少时间(不一定是他自己到capital，可以是别人帮他） N<=100000 3 ≤ N ≤ 100 000 0 ≤ Si≤ 10^9 1 ≤ Vi≤ 10^9 The length of each road will not exceed 10 000 For 20% of the tests, N ≤ 2 500 For 50% of the tests, each town will have at most 2 adjacent roads (i.e., the graph of roads will be a line)
Input
N 以下N-1行A,B,C三个数表示A,B之间有一条长为C的边。 再N行每行两数Wi,Vi 输出有一行N-1个数表示如题所述。
f[w]=W[w]+V[w]*dep[w]+min(f[u]-dep[u]*V[w]) u在w到根的路径上
树上的斜率优化，两维分别是深度dep和答案f，dfs并用单调栈记录当前点到根路径上的凸包，三分得到决策点
为保证时间复杂度，单调栈pop时要用二分确定弹出的元素个数，并支持撤销
#include<cstdio>typedef long double ld;typedef long long i64;const int N=100007;int n,es[N*2],enx[N*2],ev[N*2],e0[N],ep=2;int c[N],v[N],ss[N],sp=0;i64 f[N],dep[N];int _(){ int x; scanf("%d",&x); return x;}bool chk(int a,int b,int w){ return (f[b]-f[a])/ld(dep[b]-dep[a])>(f[w]-f[b])/ld(dep[w]-dep[b]);}void f1(int w,int pa){ if(sp){ int L=1,R=sp,M; while(L<R){ M=(L+R)>>1; int a=ss[M],b=ss[M+1]; if(f[a]-f[b]<v[w]*(dep[a]-dep[b]))R=M; else L=M+1; } f[w]=c[w]+v[w]*(dep[w]-dep[ss[L]])+f[ss[L]]; } int L=1,R=sp,M; if(L<R&&!chk(ss[R-1],ss[R],w))L=R; while(L<R){ M=(L+R)>>1; if(chk(ss[M],ss[M+1],w))R=M; else L=M+1; } L=sp; M=ss[sp=R+1]; ss[sp]=w; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u==pa)continue; dep[u]=dep[w]+ev[i]; f1(u,w); } ss[sp]=M; sp=L;}int main(){ n=_(); for(int i=1,a,b,c;i<n;++i){ a=_();b=_();c=_(); es[ep]=b;enx[ep]=e0[a];ev[ep]=c;e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];ev[ep]=c;e0[b]=ep++; } for(int i=2;i<=n;++i){ c[i]=_(); v[i]=_(); } f1(1,0); for(int i=2;i<=n;++i)printf("%lld%c",f[i],i==n?10:32); return 0;}
bzoj 1767: [Ceoi2009]harbingers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。