首页 > 代码库 > BZOJ3672: [Noi2014]购票
BZOJ3672: [Noi2014]购票
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3672
题解：填上一个大坑。。。
我还是说一下算法吧：
1）对树进行分治，每次分治一颗以x为根的树，不妨令它的重心为rt。
2）我们首先对rt分出的子树中包含x的子树进行分治。那么分治结束后x-rt的f[i]都已计算完毕。
类似于CDQ分治，考虑x-rt对下面这些子树的影响。这样我们把下面所有的点拎出来，按能到达的最远距离从小到大排序。
从rt开始向上一个个插入并且维护一个凸包，同时把下面的点可计算答案的就计算了，在凸包上二分即可。因为后面加进来的点他也到不了，现在计算完了走人。
这样我们处理了x-rt对下面的影响，然后递归分治下面的一颗颗子树即可。
复杂度nlog^2 n
下面是一些细节（细节好多啊。。。）
1）在凸包上二分可以直接把斜率存下来lower_bound。
2）树分治的时候可以给每条边一个bool can，表示该边是否已经被割断，这样就限制了树的形态。
我事先分治含x的子树时是不含rt的，然后再用x-rt更新，rt，因为如果含rt的话感觉要出现一些奇怪的问题。。。（把下面的边都禁止了，然后再查询？）
3）斜率优化每次都得从定义开始想老半天，这j，k的斜率>x说明 j比k优，然后我们要找到一个一直比前一个优的然后后来斜率<k了，这样它就是最优解。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 200000+514 #define maxm 100000+515 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)if(e[i].can)23 #define mod 100000000724 using namespace std;25 inline ll read()26 {27 ll x=0,f=1;char ch=getchar();28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30 return x*f;31 }32 int n,cnt,top,sta[maxn],head[maxn],g[maxn],tot,root,s[maxn],sum,fa[maxn],ss[maxn];33 ll d[maxn],p[maxn],q[maxn],f[maxn],lim[maxn];34 double k[maxn];35 struct edge{int go,next;ll w;bool can;}e[maxn];36 inline void add(int x,int y,ll w)37 {38 e[++tot]=(edge){y,head[x],w,1};head[x]=tot;39 }40 inline void dfs(int x)41 {42 for4(i,x)d[y]=d[fa[y]=x]+e[i].w,dfs(y);43 }44 inline void getrt(int x)45 {46 ss[x]=0;s[x]=1;47 for4(i,x){getrt(y);s[x]+=s[y];ss[x]=max(ss[x],s[y]);}48 ss[x]=max(ss[x],sum-s[x]);49 if(ss[x]<ss[root])root=x;50 }51 inline void get(int x)52 {53 g[++g[0]]=x;54 for4(i,x)get(y);55 }56 inline double slope(int x,int y)57 {58 return (double)(f[x]-f[y])/(double)(d[x]-d[y]);59 }60 inline void insert(int x)61 {62 while(top>1&&slope(x,sta[top])>slope(sta[top],sta[top-1]))top--;63 sta[++top]=x;k[top]=-slope(x,sta[top-1]);64 } 65 inline bool cmp(int x,int y){return d[x]-lim[x]>d[y]-lim[y];}66 inline void use(int x,int y)67 {68 if(d[x]-d[y]<=lim[x])f[x]=min(f[x],f[y]+(d[x]-d[y])*p[x]+q[x]);69 }70 void solve(int x)71 {72 if(sum<=1)return;73 root=0;getrt(x);int rt=root;74 for4(i,fa[rt])if(y==rt){e[i].can=0;sum=s[x]-s[y];solve(x);break;}75 for(int i=fa[rt];i!=fa[x];i=fa[i])use(rt,i);76 g[0]=0;77 for4(i,rt)get(y);78 sort(g+1,g+g[0]+1,cmp);top=0;79 for(int i=1,j=rt;i<=g[0];i++)80 {81 int y=g[i];82 for(;j!=fa[x]&&d[j]>=d[y]-lim[y];j=fa[j])insert(j);83 if(!top)continue;84 else if(top==1)use(y,sta[top]);85 else use(y,sta[min(top,upper_bound(k+2,k+top+1,-p[y])-k-1)]);86 }87 for4(i,rt){e[i].can=0;sum=s[y];solve(y);}88 } 89 int main()90 {91 freopen("input.txt","r",stdin);92 freopen("output.txt","w",stdout);93 n=read();read();ss[0]=inf;94 for2(i,2,n){int x=read(),y=read();add(x,i,y);p[i]=read();q[i]=read();lim[i]=read();f[i]=1ll<<62;}95 dfs(1);96 sum=n;solve(1);97 for2(i,2,n)printf("%lld\n",f[i]);98 return 0;99 }
BZOJ3672: [Noi2014]购票
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。