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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3242: [Noi2013]快餐店(线段树)  

2014-06-18 15:50:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


考虑如果图是一棵树的情况,那么理所当然选址是直径的中间,如果是环套树,那么由于最短路组成一棵树,所以是删去环上一条边组成的所有树的直径的最小值的一半,那么我们把环找出来,从中间一出断开,就可以用线段树求出直径在环上的情况,不在环上的情况分开处理即可。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #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 , l , r ) for ( int i = l ; i <= r ; ++ i )

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

  •  

  • typedef long long ll ;

  •  

  • const int maxn = 101000 , maxm = 201000 , inf = 0x7fffffff ;

  • const ll INF = ll( inf ) * ll( inf ) ;

  •  

  • struct edge {

  •     edge *next ;

  •     int t , d ;

  • } E[ maxm ] ;

  •  

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

  •  

  • inline void Init_edge(  ) {

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

  • }

  •  

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

  •     pt -> t = t , pt -> next = head[ s ] , pt -> d = d ;

  •     head[ s ] = pt ++ ;

  • }

  •  

  • inline void addedge( int s , int t , int d ) {

  •     add( s , t , d ) , add( t , s , d ) ;

  • }

  •  

  • int n , sta[ maxn ] , tp = 0 , pos[ maxn ] ;

  • int ve[ maxn ] , vn = 0 , dn[ maxn ] , nxt[ maxn ] , lst[ maxn ] ;

  • bool ud[ maxn ] , fg[ maxn ] ;

  •  

  • void getC( int now , int fa ) {

  •     sta[ pos[ now ] = ++ tp ] = now , ud[ now ] = true ;

  •     travel( now ) if ( p -> t != fa ) {

  •         if ( vn ) return ;

  •         dn[ now ] = p -> d ;

  •         if ( ! ud[ p -> t ] ) {

  •             getC( p -> t , now ) ;

  •         } else {

  •             REP( i , pos[ p -> t ] , tp ) {

  •                 nxt[ vn ] = dn[ ve[ vn ] = sta[ i ] ] ;

  •                 vn ++ ;

  •             }

  •             Rep( i , vn ) lst[ i ] = nxt[ ( i - 1 + vn ) % vn ] , fg[ ve[ i ] ] = true ;

  •         }

  •     }

  •     ud[ now ] = false , tp -- ;

  • }

  •  

  • inline void upd( ll &x , ll &y , ll a ) {

  •     if ( a > x ) {

  •         y = x ;

  •         x = a ;

  •     } else if ( a > y ) y = a ;

  • }

  •  

  • inline void upd0( int &v , ll &d , int _v , ll _d ) {

  •     if ( _d > d ) {

  •         d = _d , v = _v ;

  •     }

  • }

  •  

  • inline void upd1( ll &x , ll y ) {

  •     if ( y > x ) x = y ;

  • }

  •  

  • ll dep[ maxn ][ 2 ] , dpth[ maxn ] , mh , dist[ maxn ] , ans ;

  • int mv ;

  •  

  • void geth( int now , int fa ) {

  •     upd0( mv , mh , now , dpth[ now ] ) ;

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

  •         dpth[ p -> t ] = dpth[ now ] + ll( p -> d ) ;

  •         geth( p -> t , now ) ;

  •     }

  • }

  •  

  • ll ans0 = 0 ;

  •  

  • inline void upd2( ll &mx , ll &mx0 , ll &mx1 , ll _mx , ll _mx0 , ll _mx1 ) {

  •     mx = max( max( mx , _mx ) , mx0 + _mx1 ) ;

  •     mx0 = max( mx0 , _mx0 ) , mx1 = max( mx1 , _mx1 ) ;

  • }

  •  

  • struct node {

  •  

  •     node *lc , *rc ;

  •     int l , r , mid ;

  •     ll mx , mx0 , mx1 , tag ;

  •  

  •     inline void pushdown(  ) {

  •         if ( tag ) {

  •             mx0 += tag , mx1 -= tag ;

  •             if ( l < r ) {

  •                 lc -> tag += tag , rc -> tag += tag ;

  •             }

  •             tag = 0 ;

  •         }

  •     }

  •  

  •     inline void update(  ) {

  •         pushdown(  ) ;

  •         if ( l < r ) {

  •             lc -> pushdown(  ) , rc -> pushdown(  ) ;

  •             upd2( mx = lc -> mx , mx0 = lc -> mx0 , mx1 = lc -> mx1 , rc -> mx , rc -> mx0 , rc -> mx1 ) ;

  •         }

  •     }

  •  

  • } sgt[ maxn << 1 ] ;

  •  

  • typedef node* np ;

  •  

  • np ptt = sgt , root ;

  •  

  • void build( int l , int r , np &t ) {

  •     t = ptt ++ ;

  •     t -> l = l , t -> r = r ;

  •     if ( l == r ) {

  •         t -> mx = 0 , t -> mx0 = dep[ l ][ 0 ] - dist[ l ] , t -> mx1 = dep[ l ][ 0 ] + dist[ l ] , t -> tag = 0 ;

  •         return ;

  •     }

  •     t -> mid = ( l + r ) >> 1 ;

  •     build( l , t -> mid , t -> lc ) , build( t -> mid + 1 , r , t -> rc ) ;

  •     t -> update(  ) ;

  • }

  •  

  • void dec( int l , int r , ll d , np t ) {

  •     t -> pushdown(  ) ;

  •     if ( t -> l == l && r == t -> r ) {

  •         t -> tag += d ; return ;

  •     }

  •     if ( r <= t -> mid ) dec( l , r , d , t -> lc ) ; else

  •         if ( l > t -> mid ) dec( l , r , d , t -> rc ) ; else

  •             dec( l , t -> mid , d , t -> lc ) , dec( t -> mid + 1 , r , d , t -> rc ) ;

  •     t -> update(  ) ;

  • }

  •  

  • void change( int pos , ll mx0 , ll mx1 , np t ) {

  •     t -> pushdown(  ) ;

  •     if ( t -> l == t -> r ) {

  •         t -> mx = 0 , t -> mx0 = mx0 , t -> mx1 = mx1 ; return ;

  •     }

  •     change( pos , mx0 , mx1 , pos <= t -> mid ? t -> lc : t -> rc ) ;

  •     t -> update(  ) ;

  • }

  •  

  • void query( int l , int r , ll &mx , ll &mx0 , ll &mx1 , np t ) {

  •     if ( l > r ) {

  •         mx = mx0 = mx1 = 0 ; return ;

  •     }

  •     t -> pushdown(  ) ;

  •     if ( l == t -> l && r == t -> r ) {

  •         mx = t -> mx , mx0 = t -> mx0 , mx1 = t -> mx1 ;

  •         return ;

  •     }

  •     if ( r <= t -> mid ) query( l , r , mx , mx0 , mx1 , t -> lc  ) ; else

  •         if ( l > t -> mid ) query( l , r , mx , mx0 , mx1 , t -> rc ) ; else {

  •             query( l , t -> mid , mx , mx0 , mx1 , t -> lc ) ;

  •             ll a , b , c ; query( t -> mid + 1 , r , a , b , c , t -> rc ) ;

  •             upd2( mx , mx0 , mx1 , a , b , c ) ;

  •         }

  • }

  •  

  • int main(  ) {

  •     Init_edge(  ) ;

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

  •     rep( i , n ) {

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

  •     }

  •     memset( pos , 0 , sizeof( pos ) ) , memset( ud , false , sizeof( ud ) ) , memset( fg , false , sizeof( fg ) ) ;

  •     getC( 1 , 0 ) ;

  •     Rep( i , vn ) {

  •         dep[ i ][ 0 ] = dep[ i ][ 1 ] = 0 ;

  •         int now = ve[ i ] ;

  •         travel( now ) if ( ! fg[ p -> t ] ) {

  •             dpth[ p -> t ] = mh = ll( p -> d ) ;

  •             geth( p -> t , now ) ;

  •             upd( dep[ i ][ 0 ] , dep[ i ][ 1 ] , mh ) ;

  •             dpth[ mv ] = mh = 0 ;

  •             geth( mv , 0 ) ;

  •             upd1( ans , mh ) ;

  •         }

  •         upd1( ans , dep[ i ][ 0 ] + dep[ i ][ 1 ] ) ;

  •     }

  •     ll temp = INF , a , b , c , x , y , z , sum = 0 ;

  •     dist[ 0 ] = 0 ;

  •     REP( i , 1 , ( vn - 1 ) ) dist[ i ] = dist[ i - 1 ] + ll( nxt[ i - 1 ] ) ;

  •     Rep( i , vn ) sum += nxt[ i ] ;

  •     build( 0 , vn - 1 , root ) ;

  •     Rep( i , vn ) {

  •         query( i , vn - 1 , a , b , c , root ) ;

  •         if ( i ) {

  •             query( 0 , i - 1 , x , y , z , root ) ;

  •             upd2( a , b , c , x , y , z ) ;

  •         }

  •         if ( a < temp ) temp = a ;

  •         dec( 0 , vn - 1 , nxt[ i ] , root ) ;

  •         ll d = sum - nxt[ i ] ;

  •         change( i , dep[ i ][ 0 ] - d , dep[ i ][ 0 ] + d , root ) ;

  •     }

  •     ans = max( ans , temp ) ;

  •     printf( "%.1f\n" , double( ans ) / 2.0 ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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