首页 > 代码库 > bzoj 3672 购票 点分治+dp

bzoj 3672 购票 点分治+dp

2024-09-13 22:07:14   217人阅读

3672: [Noi2014]购票

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 1177  Solved: 562
[Submit][Status][Discuss]

Description

 今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。
       全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 fv  以及到父亲城市道路的长度 sv。
从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。
对于任意一个城市 v，我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 lv  时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 pv,qv  作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dpv+qv。
每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。
 
 
列出dp方程后是一个很简单的斜率优化的形式，需要维护右下凸壳，转移的时候在上边二分。(开始的时候脑子不清醒先写了个左下凸壳又改成了左上凸壳)
我们可以类似CDQ分治用点分治来处理转移。
每回找到重心后先递归处理深度比较浅的那部分，处理浅的和重心对深的的影响，在处理深的一部分(如同CDQ求LIS，先递归左半边再处理转移)。
反正我是每回求完浅的部分后暴力求了一下重心的f。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#define ll long long#define inf 1e17#define N 200005using namespace std;int n,t;int head[N],ver[N*2],nxt[N*2],tot;ll quan[N*2];void add(int a,int b,ll c){	tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;quan[tot]=c;return ;}int fa[N],d[N];ll s[N],p[N],q[N],l[N],dep[N],f[N];void dfs(int x,int ff){	for(int i=head[x];i;i=nxt[i])	{		if(ver[i]==ff)continue;		dep[ver[i]]=dep[x]+quan[i];		d[ver[i]]=d[x]+1;		dfs(ver[i],x);	}	return ;}int mn,zhong;int size[N],now,v[N];void dffs(int x,int ff){	int mx=0;size[x]=1;	for(int i=head[x];i;i=nxt[i])	{		if(v[ver[i]]||ver[i]==ff)continue;		dffs(ver[i],x);		size[x]+=size[ver[i]];		if(size[ver[i]]>mx)mx=size[ver[i]];	}if(now-size[x]>mx)mx=now-size[x];	if(mx<mn)mn=mx,zhong=x;	return ;}int tp[N],top;void dfss(int x,int ff){	for(int i=head[x];i;i=nxt[i])	{		if(v[ver[i]]||ver[i]==ff)continue;		tp[++top]=ver[i];		dfss(ver[i],x);	}}bool cmp(int x,int y){	return dep[x]-l[x]>dep[y]-l[y];}int g[N];int as[N],cnt;double cj(ll x,ll y,ll xx,ll yy){	return (double)x*yy-(double)y*xx;}double xie[N];void dp(){	int pt=1;int r=0;	for(int i=1;i<=top;i++)	{		int x=tp[i];		while(pt!=cnt+1&&dep[x]-l[x]<=dep[as[pt]])		{			while(r>1&&cj(dep[as[g[r]]]-dep[as[pt]],f[as[g[r]]]-f[as[pt]],dep[as[g[r-1]]]-dep[as[pt]],f[as[g[r-1]]]-f[as[pt]])<=0)r--;			g[++r]=pt;			if(r!=1)xie[r]=(double)(f[as[pt]]-f[as[g[r-1]]])/(double)(dep[as[pt]]-dep[as[g[r-1]]]);			pt++;		}xie[1]=1e100;		if(!r)continue;		int ha=1,ta=r;		while(ha<=ta)		{			int mid=(ha+ta)>>1;			if(xie[mid]>=p[x])ha=mid+1;			else ta=mid-1;		}		f[x]=min(f[x],f[as[g[ta]]]+(dep[x]-dep[as[g[ta]]])*p[x]+q[x]);	}}int id;void ds(int x,int ff){	size[x]=1;if(d[x]<mn)mn=d[x],id=x;	for(int i=head[x];i;i=nxt[i])	{		if(ver[i]==ff||v[ver[i]])continue;		ds(ver[i],x);		size[x]+=size[ver[i]];	}}void solve(int x){	now=size[x];mn=n+1;zhong=x;	dffs(x,-1);	int root=zhong;v[root]=1;mn=n+1;	ds(root,-1);int pp=id;	for(int i=head[root];i;i=nxt[i])	{		if(!v[ver[i]]&&ver[i]==fa[root])solve(ver[i]);	}	cnt=0;as[++cnt]=root;	for(int i=fa[root];i!=fa[pp];i=fa[i])	{		as[++cnt]=i;		if(dep[root]-dep[i]<=l[root])f[root]=min(f[root],f[i]+(dep[root]-dep[i])*p[root]+q[root]);	}	top=0;	dfss(root,-1);	sort(tp+1,tp+top+1,cmp);	dp();	for(int i=head[root];i;i=nxt[i])	{		if(!v[ver[i]])solve(ver[i]);	}	return ;}int main(){	scanf("%d%d",&n,&t);	for(int i=2;i<=n;i++)	{		scanf("%d%lld%lld%lld%lld",&fa[i],&s[i],&p[i],&q[i],&l[i]);		add(fa[i],i,s[i]);add(i,fa[i],s[i]);	}	for(int i=2;i<=n;i++)f[i]=inf;	d[1]=1;dfs(1,-1);	size[1]=n;solve(1);	for(int i=2;i<=n;i++)	{		printf("%lld\n",f[i]);	}	return 0;}

　　

 

bzoj 3672 购票 点分治+dp


联系
我们