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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1509: [NOI2003]逃学的小孩(树DP)  

2014-07-15 23:08:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


难得的水题啊~

我们可以发现,最优解一定是A,B的链中间长出一个C(或者连到C的链)(反证),这样我们可以枚举他们中间的那个点,然后用树DP预先算出某个点向上连出的最长链长度,向下连出的最长链长度,每次枚举的时候选出改点最长的三条链分别为a,b,c,那么答案就是a+b+c+min(a,b)。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •   

  • using namespace std ;

  •   

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

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

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

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  •   

  • const int maxn = 201000 ;

  • const int maxm = 401000 ;

  •   

  • struct edge {

  •         edge *next ;

  •         int t , d ;

  • } E[ maxm ] ;

  •   

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

  •   

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

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

  • }

  •   

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

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

  • }

  •   

  • int n , m ;

  •   

  • typedef long long ll ;

  •   

  • ll dp[ maxn ][ 2 ] , ans = 0 , D[ maxn ] ;

  • int ch[ maxn ] ;

  •   

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

  •   

  • void dfs0( int now , int fa ) {

  •         ll ret = 0 ;

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

  •                 dfs0( p -> t , now ) ; ret = max( ret , dp[ p -> t ][ 0 ] + ll( p -> d ) ) ;

  •         }

  •         dp[ now ][ 0 ] = ret ;

  • }

  •   

  • void dfs1( int now , int fa ) {

  •         ll mx = dp[ now ][ 1 ] ;

  •         int cnt = 0 , v ;

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

  •                 ch[ ++ cnt ] = p -> t ; D[ cnt ] = p -> d ;

  •                 dp[ p -> t ][ 1 ] = mx + ll( p -> d ) ;

  •                 mx = max( mx , dp[ p -> t ][ 0 ] + ll( p -> d ) ) ;

  •         }

  •         mx = dp[ now ][ 1 ] ;

  •         DOWN( i , cnt , 1 ) {

  •                 v = ch[ i ] ;

  •                 dp[ v ][ 1 ] = max( dp[ v ][ 1 ] , mx + D[ i ] ) ;

  •                 mx = max( mx , dp[ v ][ 0 ] + D[ i ] ) ;

  •         }

  •         travel( now ) if ( p -> t != fa ) dfs1( p -> t , now ) ;

  • }

  •   

  • void dfs2( int now , int fa ) {

  •         ll a = dp[ now ][ 1 ] , b = 0 , c = 0 , cost ;

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

  •                 if ( ( cost = dp[ p -> t ][ 0 ] + ll( p -> d ) ) > a ) {

  •                         c = b ; b = a ; a = cost ;

  •                 } else if ( cost > b ) {

  •                         c = b ; b = cost ;

  •                 } else if ( cost > c ) c = cost ;

  •         }

  •         ans = max( ans , c + a + b + min( a , b ) ) ;

  •         travel( now ) if ( p -> t != fa ) dfs2( p -> t , now ) ;

  • }

  •   

  • int main(  ) {

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

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

  •         while ( m -- ) {

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

  •         }

  •         dfs0( 1 , 0 ) ; dp[ 1 ][ 1 ] = 0 ; dfs1( 1 , 0 ) ; dfs2( 1 , 0 ) ;

  •         printf( "%lld\n" , ans ) ;

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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