bzoj 1758 [Wc2010]重建计划分数规划+树分治单调队列check

[Wc2010]重建计划

Time Limit: 40 Sec Memory Limit: 162 MB
Submit: 4345 Solved: 1054
[Submit][Status][Discuss]

Description

bzoj 1758 [Wc2010]重建计划分数规划+树分治单调队列check-LMLPHP

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

题解：点分上是一个log，二分是一个log，然后是单调队列判断，n，总复杂度O(nlogn^2)

hzwer的代码十分不优秀，应该是按照最低深度从小到大去个棵子树去判断才可以，不然是不行的，

不然会是复杂度退化成n^2

改了比较siz还是T，不知道为什么了。

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstdlib>

 #include<vector>

 #define inf 1000000007

 #define eps 0.0001

 #define N 100007

 #define M 200007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,S,L,U,rt,lim;

 double ans;

 int cnt,hed[N],rea[M],val[M],nxt[M];

 int sz[N],fa[N],f[N],dep[N];

 int q[N],dq[N];

 bool flag[N];

 double dis[N],mx[N];

 int num[N*],xz,shu[N*];

 void add(int u,int v,int w)

 {

     nxt[++cnt]=hed[u];

     hed[u]=cnt;

     rea[cnt]=v;

     val[cnt]=w;

 }

 void get_root(int u,int fa)

 {

     sz[u]=,f[u]=;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (v==fa||flag[v]) continue;

         get_root(v,u);

         sz[u]+=sz[v];

         f[u]=max(f[u],sz[v]);

     }

     f[u]=max(f[u],S-sz[u]);

     if (f[u]<=f[rt])rt=u;

 }

 bool check(int rt,double zhi)

 {

     int up=;

     for (int i=hed[rt];i!=-;i=nxt[i])

     {

         int v=rea[i];double fee=(double)val[i]-zhi;

         if (flag[v])continue;

         int hd=,tl=;

         q[]=v;

         fa[v]=rt,dep[v]=;

         dis[v]=fee;

         while(hd!=tl)

         {

             int now=q[hd];hd++;

             for (int i=hed[now];i!=-;i=nxt[i])

             {

                 int v=rea[i];double fee=(double)val[i]-zhi;

                 if (v==fa[now]||flag[v])continue;

                 q[tl++]=v;

                 fa[v]=now,dep[v]=dep[now]+;

                 dis[v]=dis[now]+fee;

             }

         }

         int l=,r=,now=up;

         for (int i=;i<tl;i++)

         {

             int x=q[i];

             while(dep[x]+now>=L&&now>=)

             {

                 while(l<=r&&mx[dq[r]]<mx[now])r--;

                 dq[++r]=now;

                 now--;

             }

             while(l<=r&&dep[x]+dq[l]>U)l++;

             if (l<=r&&dis[x]+mx[dq[l]]>=)return ;

         }

         for (int i=up+;i<=dep[q[tl-]];i++)mx[i]=-inf;

         for (int i=;i<tl;i++)

         {

             int x=q[i];

             mx[dep[x]]=max(mx[dep[x]],dis[x]);

         }

         up=max(up,dep[q[tl-]]);

     }

     return ;

 }

 void cal(int u)//可以

 {

     double l=ans,r=lim,mid;

     while(r-l>eps)

     {

         mid=(l+r)/;

         if(check(u,mid))l=mid;

         else r=mid;

     }

     ans=l;

 }

 bool cmp(int x,int y)

 {

     return shu[x]<shu[y];

 }

 void solve(int u)

 {

     cal(u);

     flag[u]=;int yl=xz,Sum=S;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (flag[v])continue;

         rt=;

         if (sz[v]<sz[u])S=sz[v];

         else S=Sum-sz[u];

         get_root(v,);

         if(sz[v]>L)num[++xz]=rt,shu[++xz]=S;

     }

     sort(num+yl+,num+xz+,cmp);

     for (int i=yl+;i<=xz;i++)

         solve(num[i]);

     xz=yl;

 }

 int main()

 {

     memset(hed,-,sizeof(hed));

     n=read(),L=read(),U=read();

     for (int i=;i<n;i++)

     {

         int u=read(),v=read(),w=read();

         add(u,v,w),add(v,u,w);

         lim=max(lim,w);

     }

     f[]=n;

     rt=,S=n;

     get_root(,);

     solve(rt);

     printf("%.3lf",ans);

 }

重建