注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1758: [Wc2010]重建计划(点分治+二分)  

2014-05-27 12:55:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1758


分数规划问题,经典做法二分答案,然后由于是树的路径问题,所以在点分治里面套一个二分,然后对于求max{a[i]+b[j]}(L<=i+j<=R),转化成( L-i <= j <= R-i ),那么就出现一个左右端点都单调的RMQ问题,那就单调队列,然后由于树分治每次递归调用的复杂度必须只与子树的大小相关,那么必须按照当前分治的重心的子树最大高度从小到大枚举子树,这样才能保证总共的复杂度为O(n log n log MaxV)。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  •  

  • using namespace std ;

  •  

  • #define addedge( s , t , d ) add( s , t , d ) , add( t , s , d )

  • #define travel( x ) for ( edge *p = Head[ x ] ; p ; p = p -> next )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define REP( i , a , b ) for ( int i = a ; i <= b ; ++ i )

  • #define DOWN( i , b , a ) for ( int i = b ; i >= a ; -- i )

  •  

  • const int maxn = 101000 , inf = 100000000 ;

  • const double esp = 0.0001 ;

  •  

  • struct edge {

  •     int t , d ;

  •     edge *next ;

  • } E[ maxn << 1 ] ;

  •  

  • edge *pt = E , *Head[ maxn ] ;

  •  

  • void add( int s , int t , int d ) {

  •     edge *p = pt ++ ;

  •     p -> t = t , p -> d = d , p -> next = Head[ s ] ;

  •     Head[ s ] = p ;

  • }

  •  

  • double ans = 0 ;

  • bool used[ maxn ] ;

  • int n , L , R ;

  •  

  • int size[ maxn ] , maxw , h[ maxn ] , maxh[ maxn ] , MAXH , root ;

  • double dep[ maxn ] ;

  • vector < int > sub[ maxn ] , tub[ maxn ] ;

  •  

  • inline void Upd( int &pos , int val ) {

  •     if ( val > pos ) pos = val ;

  • }

  •  

  • inline void upd( double &pos , double val ) {

  •     if ( val > pos ) pos = val ;

  • }

  •  

  • void getsize( int now , int fa ) {

  •     size[ now ] = 1 ;

  •     travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {

  •         getsize( p -> t , now ) , Upd( maxw , p -> d ) ;

  •         size[ now ] += size[ p -> t ] ;

  •     }

  • }

  •  

  • int q[ maxn ][ 2 ] , head , tail ;

  •  

  • inline void getroot( int now ) {

  •     bool flag ;

  •     int ve , pre , si = size[ now ] >> 1 ;

  •     q[ tail = 1 ][ 0 ] = now , q[ 1 ][ 1 ] = 0 , head = 0 ;

  •     for ( ; head < tail ; ) {

  •         flag = true ;

  •         ve = q[ ++ head ][ 0 ] ; pre = q[ head ][ 1 ] ;

  •         if ( size[ now ] - size[ ve ] > si ) flag = false ;

  •         travel( ve ) if ( p -> t != pre && ! used[ p -> t ] ) {

  •             if ( size[ p -> t ] > si ) flag = false ;

  •             q[ ++ tail ][ 0 ] = p -> t ; q[ tail ][ 1 ] = ve ;

  •         }

  •         if ( flag ) {

  •             root = ve ; return ;

  •         }

  •     }

  • }

  •  

  • void geth( int now , int fa , int num ) {

  •     Upd( maxh[ num ] , h[ now ] ) , sub[ num ].push_back( now ) , Upd( MAXH , h[ now ] ) ;

  •     travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {

  •         h[ p -> t ] = h[ now ] + 1 , dep[ p -> t ] = dep[ now ] + p -> d ;

  •         geth( p -> t , now , num ) ;

  •     }

  • }

  •  

  • double dp[ maxn ] , fun[ maxn ] ;

  • int Q[ maxn ] ;

  •  

  • inline bool check( double mid ) {

  •     REP( i , 0 , MAXH ) dp[ i ] = - inf ; dp[ 0 ] = 0 ;

  •     double temp = - inf ;

  •     int v , u , left , right , ret ;

  •     REP( i , 0 , MAXH ) {

  •         DOWN( k , tub[ i ].size(  ) - 1 , 0 ) {

  •             v = tub[ i ][ k ] ;

  •             REP( j , 0 , maxh[ v ] ) fun[ j ] = - inf ;

  •             REP( j , 0 , ( sub[ v ].size(  ) - 1 ) ) {

  •                 u = sub[ v ][ j ] ;

  •                 upd( fun[ h[ u ] ] , dep[ u ] - double( h[ u ] ) * mid ) ;

  •             }

  •             head = 1 , tail = 0 ;

  •             left = max( L - maxh[ v ] , 0 ) , right = min( R - maxh[ v ] , maxh[ v ] ) ;

  •             REP( j , left , right ) {

  •                 for ( ; head <= tail && dp[ Q[ tail ] ] <= dp[ j ] ; -- tail ) ;

  •                 Q[ ++ tail ] = j ;

  •             }

  •             DOWN( j , maxh[ v ] , 0 ) {

  •                 for ( ; head <= tail && Q[ head ] < L - j ; ++ head ) ;

  •                 if ( head <= tail ) upd( temp , fun[ j ] + dp[ Q[ head ] ] ) ;

  •                 if ( R - ( j - 1 ) <= maxh[ v ] ) {

  •                     for ( ; head <= tail && dp[ Q[ tail ] ] <= dp[ R - ( j - 1 ) ] ; -- tail ) ;

  •                     Q[ ++ tail ] = R - ( j - 1 ) ;

  •                 }

  •             }

  •             REP( j , 0 , maxh[ v ] ) upd( dp[ j ] , fun[ j ] ) ;

  •             if ( temp >= 0 ) return true ;

  •         }

  •     }

  •     return false ;

  • }

  •  

  • void solve( int now ) {

  •     maxw = 0 ; getsize( now , 0 ) ; getroot( now ) ;

  •     h[ root ] = dep[ root ] = 0 , MAXH = 0 ;

  •     travel( root ) if ( ! used[ p -> t ] ) {

  •         h[ p -> t ] = 1 , dep[ p -> t ] = p -> d , maxh[ p -> t ] = 0 , sub[ p -> t ].clear(  ) ;

  •         geth( p -> t , root , p -> t ) ;

  •     }

  •     REP( i , 0 , MAXH ) tub[ i ].clear(  ) ;

  •     travel( root ) if ( ! used[ p -> t ] ) tub[ maxh[ p -> t ] ].push_back( p -> t ) ;

  •     double l = 0 , r = maxw , mid ;

  •     while ( r - l > esp ) {

  •         mid = ( l + r ) / 2.0 ;

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

  •     }

  •     upd( ans , l ) , used[ root ] = true ;

  •     travel( root ) if ( ! used[ p -> t ] ) {

  •         solve( p -> t ) ;

  •     }

  • }

  •  

  • int main(  ) {

  •     memset( Head , 0 , sizeof( Head ) ) ;

  •     scanf( "%d%d%d" , &n , &L , &R ) ;

  •     REP( i , 2 , n ) {

  •         int s , t , d ; scanf( "%d%d%d" , &s , &t , &d ) ; addedge( s , t , d ) ;

  •     }

  •     memset( used , false , sizeof( used ) ) ;

  •     solve( 1 ) ;

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

  •     return 0 ;

  • }



  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017