首页 > 代码库 > bzoj1758 [Wc2010]重建计划

bzoj1758 [Wc2010]重建计划

Description

技术分享

Input

第一行包含一个正整数N,表示X国的城市个数. 第二行包含两个正整数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

 

正解:分数规划+点分治+单调队列?。

好吧这题我是压常数过去的,并没有用单调队列。。

显然,外层二分答案,然后每条边都减去$mid$,判断是否能找到长度属于$[l,r]$且路径和$>0$的路径。

那么我们点分治,在每一层依次递归重心的所有子树,合并答案就行了,但是属于$[l,r]$这个条件不好处理。正解似乎是单调队列,然而我用的是线段树,复杂度多一个$log$。。

不过还是跑过去了,具体是怎么压常数的呢?

1.加$register$,可以快$2s$。

2.手写$min$,$max$函数,使用三目运算符,可以快将近$1s$。

3.如果当前答案已经$>0$,直接退出分治,但是这个好像对于特意构造的数据作用不大。

4.把每棵子树中深度相同的结点权值直接取$max$,并且记下这些深度,这样可以节省线段树的插入。

5.预处理出所有的重心和在每一层的最大深度,可以快$1s$。

6.用$zkw$线段树,且因为线段树是以深度为区间的,所以我们每一层分治时的线段树就以当前最大深度为上界,这样线段树消耗的$log$可以大大减少。应该说,这个压常是最优秀的,它让线段树的$log$几乎变成了常数,我大概计算了一下,每层改变线段树上界好像使得$log^{2}n$变成了$3log$左右的常数?

大概用这些压常技巧,就能通过这题了。

 

  1 //It is made by wfj_2048~  2 #include <algorithm>  3 #include <iostream>  4 #include <complex>  5 #include <cstring>  6 #include <cstdlib>  7 #include <cstdio>  8 #include <vector>  9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define inf (1e18) 15 #define eps (3e-4) 16 #define N (100010) 17 #define ls (x<<1) 18 #define rs (x<<1|1) 19 #define il inline 20 #define RG register 21 #define ll long long 22 #define min(a,b) (a<b ? a : b) 23 #define max(a,b) (a>b ? a : b) 24 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 25   26 using namespace std; 27   28 struct edge{ int nt,to,dis; }g[N<<1]; 29   30 int head[N],st[N],vi[N],vi1[N],vis[N],dep[N],son[N],sz[N],ss[N],RT[N][19],Dp[N][19],n,l,r,num,top,bit,Mx_dep; 31 double sum[N<<2],dis[N],mx[N],L,R,mid,res,ans; 32   33 il int gi(){ 34     RG int x=0,q=1; RG char ch=getchar(); 35     while ((ch<0 || ch>9) && ch!=-) ch=getchar(); 36     if (ch==-) q=-1,ch=getchar(); 37     while (ch>=0 && ch<=9) x=x*10+ch-48,ch=getchar(); 38     return q*x; 39 } 40   41 il void insert(RG int from,RG int to,RG int dis){ 42     g[++num]=(edge){head[from],to,dis},head[from]=num; return; 43 } 44  45 il void build(){ for (RG int i=1;i<=bit+n;++i) sum[i]=-inf; return; } 46  47 il void update0(RG int x,RG double y){ 48     for (x+=bit,sum[x]=max(sum[x],y),x>>=1;x;x>>=1) sum[x]=max(sum[ls],sum[rs]); return; 49 } 50  51 il void update1(RG int x){ 52     for (sum[x+=bit]=-inf,x>>=1;x;x>>=1) sum[x]=-inf; return; 53 } 54  55 il double query(RG int l,RG int r){ 56     RG double res=-inf; 57     for (l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){ 58     if (~l&1) res=max(res,sum[l^1]); 59     if (r&1) res=max(res,sum[r^1]); 60     } 61     return res; 62 } 63  64 il void getroot(RG int x,RG int p,RG int S,RG int &rt){ 65     sz[x]=1,son[x]=0; RG int v; 66     for (RG int i=head[x];i;i=g[i].nt){ 67     v=g[i].to; if (v==p || vis[v]) continue; 68     getroot(v,x,S,rt),sz[x]+=sz[v]; 69     son[x]=max(son[x],sz[v]); 70     } 71     son[x]=max(son[x],S-sz[x]); 72     if (son[rt]>=son[x]) rt=x; return; 73 } 74  75 il void getdep(RG int x,RG int p){ 76     dep[x]=dep[p]+1,Mx_dep=max(Mx_dep,dep[x]); RG int v; 77     for (RG int i=head[x];i;i=g[i].nt){ 78     v=g[i].to; if (v==p || vis[v]) continue; 79     getdep(v,x); 80     } 81     return; 82 } 83  84 il void getdis(RG int x,RG int p,RG double key){ 85     dep[x]=dep[p]+1,sz[x]=1; RG int v,k=dep[x]; 86     if (!vi[k]) st[++top]=k,vi[k]=1; mx[k]=max(mx[k],dis[x]); 87     for (RG int i=head[x];i;i=g[i].nt){ 88     v=g[i].to; if (v==p || vis[v]) continue; 89     dis[v]=dis[x]+g[i].dis-key; 90     getdis(v,x,key),sz[x]+=sz[v]; 91     } 92     return; 93 } 94  95 il void solve0(RG int x,RG int S,RG int level){ 96     RG int rt=0,v; Mx_dep=0,son[0]=S; 97     getroot(x,0,S,rt),vis[rt]=1,RT[x][level]=rt; 98     for (RG int i=head[rt];i;i=g[i].nt){ 99     v=g[i].to; if (!vis[v]) getdep(v,0);100     }101     Dp[x][level]=Mx_dep;102     for (RG int i=head[rt];i;i=g[i].nt){103     v=g[i].to; if (!vis[v]) solve0(v,sz[v],level+1);104     }105     return;106 }107 108 il int solve(RG int x,RG int S,RG int level,RG double key){109     RG int rt=RT[x][level],Mx=Dp[x][level],tp=0,v; vis[rt]=1;110     for (bit=1;bit<=Mx+1;bit<<=1);111     for (RG int i=head[rt];i;i=g[i].nt){112     v=g[i].to; if (vis[v]) continue;113     top=0,dis[v]=g[i].dis-key,getdis(v,0,key);114     for (RG int j=1,L,R,k;j<=top;++j){115         k=st[j]; if (l<=k && k<=r) res=max(res,mx[k]); if (res>eps) return 1;116         if (!vi1[k]) ss[++tp]=k,vi1[k]=1; L=max(l-k,1),R=min(r-k,Mx);117         if (L<=R) res=max(res,mx[k]+query(L,R)); if (res>eps) return 1;118     }119     for (RG int j=1,k;j<=top;++j)120         k=st[j],update0(k,mx[k]),mx[k]=-inf,vi[k]=0;121     }122     for (RG int i=1;i<=tp;++i) update1(ss[i]),vi1[ss[i]]=0;123     for (RG int i=head[rt];i;i=g[i].nt){124     v=g[i].to; if (!vis[v]) if (solve(v,sz[v],level+1,key)) return 1;125     }126     return res>eps;127 }128 129 il void work(){130     n=gi(),l=gi(),r=gi(),L=inf;131     for (RG int i=1,u,v,w;i<n;++i)132     u=gi(),v=gi(),w=gi(),insert(u,v,w),insert(v,u,w),L=min(L,w),R=max(R,w);133     solve0(1,n,0);134     while (R-L>eps){135     mid=(L+R)*0.5,res=-inf; for (bit=1;bit<=n+1;bit<<=1); build();136     for (RG int i=1;i<=n;++i) mx[i]=-inf,vi[i]=vi1[i]=vis[i]=0;137     if (solve(1,n,0,mid)) ans=mid,L=mid; else R=mid;138     }139     printf("%0.3lf\n",ans); return;140 }141  142 int main(){143     File("rebuild");144     work();145     return 0;146 }

 

bzoj1758 [Wc2010]重建计划