bzoj1758 [Wc2010]重建计划

bzoj1758 [Wc2010]重建计划

​​第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号

Output

输出最大平均估值，保留三位小数

Sample Input

4

2 3

1 2 1

1 3 2

1 4 3 Sample Output 2.500 HINT

N<=100000,1<=L<=U<=N-1,Vi<=1000000 新加数据一组 By leoly,但未重测..2016.9.27 新加一组数据是leoly学长加的orz 虽然网上有人吐槽 但是我仍然觉得挺好的 据说这组数据是扫把形的 题意：求最大的比率即路径权值和/路径条数和的比值最大 首先这是一个分数规划的问题 考虑如何算这个最大值 我们不妨假设现在的最大值是x那么一定满足∑i=1nw[i]n>x 我们不妨去二分一下这个x 然后将其变化为∑i=1nw[i]−n∗x>0 这个数能否> 0即可 大于0说明我的最大值还可以大 那这题对于每一条路径我都可以通过枚举过根的一条路径去搞出来 所以采用点分的方法 对于这题比较卡常 所以选择在点分里面去二分这个答案 如何验证答案 我每次算出我分治块里的最大值即可 一直取max对于整个块大小< L的点我可以选择忽略 减小常数 如何去求最大能否满足条件 设f[i]表示我当前点分的时候做的这个子树深度为i的dis的最大值 这个dis我已经提前预处理的时候-mid了 g[i]表示我之前所有做过的子树中深度i的最大值是多少 每次我相当于枚举f[i]然后去g中找一个滑动的窗口中的最大值可以单调队列来搞 比较麻烦然后比较下能否> 0如果大于0直接退出即可 注意坑点：退出之后需要将f[],g[]数组重置之后再退出 关于学长这组数据卡的是什么 其实是个小tips 就是我枚举子树的时候需要从深度小的开始向深度大的枚举 这样避免了先做了大的然后每次初始化单调队列和清空f[]数组时所带来的复杂度退化 关于这部分看下代码即可明白 优化：每次二分的L直接设定成上一次的答案即可 因为我至少已经有上一次的答案了 如果不满足那么下界也是上一次的答案

#include#include#include#include#define inf 0x3f3f3f3f#define N 110000#define pa pair#define eps 1e-4using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x;}struct node{ int y,z,next;}data[N<<1];int ff[N],h[N],root,sum,size[N],dep[N],L,R,num,n;double ans,g[N],f[N],dis[N];bool visit[N];inline void get_root(int x,int fa){ ff[x]=0;size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (visit[y]||y==fa) continue; get_root(y,x);size[x]+=size[y];ff[x]=max(ff[x],size[y]); }ff[x]=max(ff[x],sum-size[x]); if (ff[root]>ff[x]) root=x;}struct node1{ int y,size,z;}qq[N];int max1=0;inline void dfs1(int x,int fa,double mid){ f[dep[x]]=max(f[dep[x]],dis[x]);max1=max(max1,dep[x]); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z;if (y==fa||visit[y]) continue; dep[y]=dep[x]+1;dis[y]=dis[x]+z-mid;dfs1(y,x,mid); }}inline bool check(int x,double mid){ int max_deep=0;dep[x]=0;dis[x]=0;bool flag=0; for (int i=1;i<=num;++i){ int y=qq[i].y,z=qq[i].z;max1=0;dequeq;f[0]=0; dep[y]=dep[x]+1;dis[y]=dis[x]+z-mid;dfs1(y,x,mid);max_deep=max(max_deep,max1); for (int j=max_deep;j>=L;--j) { while(!q.empty()&&g[j]>g[q.back()]) q.pop_back();q.push_back(j); } for (int j=0;j<=max1;++j){ while(!q.empty()&&j+q.front()>R) q.pop_front(); if (!q.empty()) if (f[j]+g[q.front()]-eps>0) {flag=1;break;} while(!q.empty()&&L-j-1>=0&&g[L-j-1]>g[q.back()]) q.pop_back();q.push_back(L-j-1); } for (int j=0;j<=max1;++j) g[j]=max(g[j],f[j]),f[j]=-inf; if (flag) break; } for (int i=0;i<=max_deep;++i) g[i]=-inf;if(flag) return 1;else return 0;}inline bool cmp(node1 a,node1 b){return a.sizesize[x]) size[y]=sum-size[x]; qq[++num].size=size[y];qq[num].y=y;qq[num].z=data[i].z; } sort(qq+1,qq+num+1,cmp);double l=ans,r=1e6; while(r-l>eps){ double mid=(l+r)/2; if (check(x,mid)) l=mid;else r=mid; }ans=max(ans,l); for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (visit[y]) continue; root=0;sum=size[y];get_root(y,x);solve(root); }}int main(){ freopen("bzoj1758.in","r",stdin); n=read();L=read();R=read(); for (int i=0;i<=n;++i) f[i]=g[i]=-inf; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。