BZOJ1758: [Wc2010]重建计划

时间：2023-03-08 20:12:22

题解：

这题我居然做了一星期？。。。

平均值的极值其实也可以算是一种分数规划，只不过分母上b[i]=1

然后我们就可以二分这个值。类似与 HNOI最小圈

如果没有 链的长度的限制的话，我们直接两遍dfs就可以求出以每个点为起点的最长链，然后看看有没有权值和>0的即可。

但现在链有长度限制。。。

所以膜拜题解。。。

发现我们可以点分治，然后每个节点的合法对象都是一段连续的区间，

当用某个值来更新答案的时候是一个连续的区间。

所以可以单调队列来维护定长的区间最大值问题。

实现的时候好多细节。。。还好卡时过了。。。

注意优化：如果子树节点个数<l就不要递归下去了。

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 200000+5

 #define maxm 200000+5

 #define eps 1e-10

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)

 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)

 #define mod 1000000007

 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+ch-'';ch=getchar();}

     return x*f;

 }

 int n,ll,rr,mx[],rt,sum,tot,v[maxn],s[maxn],ss[maxn],head[maxn],q[maxn];

 double mid,f[maxn],g[maxn];

 struct edge{int go,next;double w;}e[*maxn];

 bool del[maxn];

 inline void add(int x,int y,double w)

 {

     e[++tot]=(edge){y,head[x],w};head[x]=tot;

     e[++tot]=(edge){x,head[y],w};head[y]=tot;

 }

 inline void getrt(int x,int fa)

 {

     ss[x]=;s[x]=;

     for4(i,x)if(!del[y]&&y!=fa)

     {

         getrt(y,x);

         s[x]+=s[y];

         ss[x]=max(ss[x],s[y]);

     }

     ss[x]=max(ss[x],sum-s[x]);

     if(ss[x]<ss[rt])rt=x;

 }

 inline void get(int x,int fa,int dep,double w)

 {

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

     g[dep]=max(g[dep],w);

     for4(i,x)if(!del[y]&&y!=fa)get(y,x,dep+,w+e[i].w-mid);

 }

 bool solve(int x)

 {

     del[x]=;mx[]=;

     for4(j,x)if(!del[y])

     {

         mx[]=;

         get(y,x,,e[j].w-mid);

         int l=,r=;

         for3(i,rr,)

         {

             if(rr-i>&&rr-i<=mx[])

             {

               while(l<=r&&f[rr-i]>f[q[r]])r--;

               q[++r]=rr-i;

             }

             if(i<=mx[])

             {

              while(l<r&&q[l]+i<ll)l++;

              if(q[l]+i>=ll&&f[q[l]]+g[i]>eps)return ;

             }

         }

         mx[]=max(mx[],mx[]);

         for1(i,mx[])f[i]=max(f[i],g[i]),g[i]=-inf;

     }

     for1(i,mx[])f[i]=-inf;

     for4(i,x)if(!del[y])

     {

         sum=s[y];rt=;

         getrt(y,);

         if(solve(rt))return ;

     }

     return ;

 }

 bool check()

 {

     for1(i,n)del[i]=,g[i]=-inf,f[i]=-inf;

     sum=n;ss[rt=]=inf;

     getrt(,);

     return solve(rt);

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     ll=read();rr=read();

     double l=0.0,r;

     for1(i,n-){int x=read(),y=read();double z=read();r=max(r,z);add(x,y,z);}

     while(r-l>1e-)

     {

         mid=(l+r)/;

         if(check())l=mid;else r=mid;

     }

     printf("%.3f\n",l);

     return ;

 }

1758: [Wc2010]重建计划

Time Limit: 40 Sec  Memory Limit: 162 MB
Submit: 887  Solved: 314
[Submit][Status]

Description

BZOJ1758: [Wc2010]重建计划

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

20%的数据,N<=5000
30%的数据,N<=100000,原有方案恰好为一条路径
100%的数据,N<=100000,1<=L<=U<=N-1,Vi<=1000000

相关文章