【COGS2652】秘术「天文密葬法」(长链剖分,分数规划)
规划 分数 剖分
2023-09-11 14:14:41 时间
【COGS2652】秘术「天文密葬法」(长链剖分,分数规划)
题面
Cogs
上面废话真多,建议直接拉到最下面看一句话题意吧:
给个树,第i个点有两个权值ai和bi,现在求一条长度为m的路径,使得Σai/Σbi最小
题解
看到这个式子就是裸的分数规划吧。。。
二分一个答案\(k\),式子变成了找一条长度为\(m\)的路径(题目里面路径长度的定义是点数)
满足\(\sum a-k\sum b\le 0\)。
首先直接把\(m=-1\)也就是没有限制的点直接判掉,这个东西没有任何意义。
(其实\(m=1\)的和没有限制是一样的。。。。)
现在把每个点的点权化为\(V_i=a_i-kb_i\),要找出一条长度为\(m\)的路径使得点权和最小。
很明显,对于一个点的子树中,我们只需要维护在相同深度中,距离它的点权和最小的那个点的点权和,距离当前根节点这个东西很不好转移,直接变成距离整棵树的根节点的距离,这样子直接减一下就好了。
那么链就只有两种情况了,一种是在一个\(LCA\)的地方转一下,这个在暴力更新轻儿子贡献的时候直接算一下。另一种是根节点向下延伸了\(m\),这个在更新完了只有直接\(check\)一下就好了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 200200
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
double ans=1e18,V[MAX];
int a[MAX],b[MAX];
int n,m,md[MAX],dep[MAX],hson[MAX],len[MAX];
void dfs1(int u,int ff)
{
md[u]=dep[u]=dep[ff]+1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff)continue;
dfs1(v,u);
if(md[v]>md[hson[u]])hson[u]=v;
}
if(hson[u])md[u]=md[hson[u]];len[u]=md[u]-dep[u]+1;
}
double tmp[MAX],*f[MAX],*id=tmp;
void dfs2(int u,int ff)
{
if(hson[u])f[hson[u]]=f[u]+1,dfs2(hson[u],u);
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff||v==hson[u])continue;
f[v]=id;id+=len[v];dfs2(v,u);
}
}
void dfs(int u,int ff)
{
V[u]+=V[ff];f[u][0]=V[u];
if(hson[u])dfs(hson[u],u);
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff||v==hson[u])continue;
dfs(v,u);
for(int j=0;j<len[v];++j)
if(len[u]>m-j-1&&m-j-1>=0)ans=min(ans,f[u][m-j-1]+f[v][j]-V[u]-V[ff]);
for(int j=0;j<len[v];++j)
f[u][j+1]=min(f[u][j+1],f[v][j]);
}
if(len[u]>m)ans=min(ans,f[u][m]-V[ff]);
}
int main()
{
freopen("cdcq_b.in","r",stdin);
freopen("cdcq_b.out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)b[i]=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
if(m==-1)
{
for(int i=1;i<=n;++i)ans=min(ans,1.0*a[i]/b[i]);
printf("%.2lf\n",ans);
return 0;
}
dfs1(1,0);f[1]=id;id+=md[1];dfs2(1,1);
double l=0,r=1e9;m-=1;
while(r-l>=1e-5)
{
double mid=(l+r)/2;ans=1e18;
for(int i=1;i<=n;++i)V[i]=a[i]-mid*b[i],tmp[i]=1e18;
dfs(1,0);
if(ans<=0)r=mid;else l=mid;
}
if(l>=5e8)puts("-1");else printf("%.2lf\n",l);
return 0;
}
相关文章
- POJ3757 01分数规划
- 总结01分数规划
- 总结01分数规划
- 【CF1133E】K Balanced Teams(动态规划,单调队列)
- 【BZOJ4738/UOJ#276】汽水(点分治,分数规划)
- 【BZOJ1017】[JSOI2008]魔兽地图(动态规划)
- 【BZOJ5281】Talent Show(分数规划)
- 【CF248E】Piglet's Birthday(动态规划)
- 【BZOJ3597】方伯伯运椰子(分数规划,网络流)
- 【BZOJ1486】最小圈(分数规划)
- 【BZOJ4753】最佳团体(分数规划,动态规划)
- 【POJ3621】【洛谷2868】Sightseeing Cows(分数规划)
- 【算法】【递归与动态规划模块】换钱的种数问题
- 【BZOJ5090】组题 分数规划
- 4月11日,每天30秒,昨夜今晨一览无余/我国首条“西氢东送”管道纳入国家规划/国际机构:中国经济蓬勃复苏,展现广阔投资
- Redis开发运维实践上线部署规划之持久化设置
- POJ 3621 Sightseeing Cows (bellman-Ford + 01分数规划)
- 《师兄教你找工作——100场面试 20个offer背后的求职秘密》一1.2 短期规划
- 大数据十三五规划或年内发布 产业链迎来新一轮发展机遇
- zoj2676 Network Wars(0-1分数规划,最大流模板)
- 【bzoj2402】陶陶的难题II 分数规划+树链剖分+线段树+STL-vector+凸包+二分
- 【bzoj4898】[Apio2017]商旅 Floyd+分数规划+Spfa
- 【bzoj4819】[Sdoi2017]新生舞会 分数规划+费用流