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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1063: [Noi2008]道路设计(树DP)  

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

  下载LOFTER 我的照片书  |

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


首先想了好久才发现这是一棵树,每个点最多连一条边,最右的点不连,所以n-1条边,然后连通,所以是树。

接下来就很好做啦,dp(v,0),dp(v,1),dp(v,2)分别表示在v不在链上,在链一端,在链中间,v子树的最小不便利度,然后就可以直接dp掉了,然后考虑第二问,我们发现最小不便利度一定不是超过log n(轻重树链剖分都log n了嘛),所以f(i,j,0),f(i,j,1),f(i,j,2)分别表示三种情况下不便利值为j的情况,然后处理个前缀和dp一下,总复杂度O(n + n log n)。


代码(细节超多QAQ):

  • #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 )

  •   

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

  •   

  • const int maxn = 101000 ;

  • const int maxm = 201000 ;

  •   

  • struct edge {

  •         edge *next ;

  •         int t ;

  • } E[ maxm ] ;

  •   

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

  •   

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

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

  • }

  •   

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

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

  • }

  •   

  • bool used[ maxn ] ;

  • int n , m , q ;

  •   

  • void dfs( int now ) {

  •         used[ now ] = true ;

  •         travel( now ) if ( ! used[ p -> t ] ) dfs( p -> t ) ;

  • }

  •   

  • int dp[ maxn ][ 3 ] , ch[ maxn ] , f[ maxn ][ 3 ] , ans ;

  •   

  • const int inf = 0x7fffffff ;

  •   

  • void Dp0( int now , int fa ) {

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

  •         int cnt = 0 ;

  •         dp[ now ][ 0 ] = 0 ;

  •         travel( now ) if ( p -> t != fa ) ch[ ++ cnt ] = p -> t ;

  •         f[ 0 ][ 0 ] = 0 , f[ 0 ][ 1 ] = f[ 0 ][ 2 ] = inf ;

  •         rep( i , cnt ) {

  •                 int v = ch[ i ] ;

  •                 f[ i ][ 0 ] = max( f[ i - 1 ][ 0 ] , min( min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) , dp[ v ][ 2 ] ) + 1 ) ;

  •                 f[ i ][ 1 ] = min( max( f[ i - 1 ][ 1 ] , min( min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) , dp[ v ][ 2 ] ) + 1 ) , max( f[ i - 1 ][ 0 ] , min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) ) ) ;

  •                 f[ i ][ 2 ] = min( max( f[ i - 1 ][ 2 ] , min( min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) , dp[ v ][ 2 ] ) + 1 ) , max( f[ i - 1 ][ 1 ] , min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) ) ) ;

  •         }

  •         dp[ now ][ 0 ] = f[ cnt ][ 0 ] , dp[ now ][ 1 ] = f[ cnt ][ 1 ] , dp[ now ][ 2 ] = f[ cnt ][ 2 ] ;

  • }

  •   

  • const int maxd = 20 ;

  •   

  • typedef long long ll ;

  •   

  • int Dp[ maxn ][ maxd ][ 3 ] , sum[ maxn ][ maxd ][ 3 ] , g[ maxn ][ 3 ][ 2 ] ;

  •   

  • void Dp1( int now , int fa ) {

  •         int cnt = 0 , v , a , b , c , d ;

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

  •                 ++ cnt ; Dp1( p -> t , now ) ;

  •         }

  •         if ( ! cnt ) {

  •                 REP( i , 0 , ans ) {

  •                         Dp[ now ][ i ][ 0 ] = Dp[ now ][ i ][ 1 ] = Dp[ now ][ i ][ 2 ] = 0 ;

  •                 }

  •                 Dp[ now ][ 0 ][ 0 ] = 1 ; return ;

  •         }

  •         cnt = 0 ;

  •         travel( now ) if ( p -> t != fa ) ch[ ++ cnt ] = p -> t ;

  •         Dp[ now ][ 0 ][ 0 ] = 0 ;

  •         if ( cnt == 1 ) {

  •                 Dp[ now ][ 0 ][ 2 ] = 0 ;

  •                 Dp[ now ][ 0 ][ 1 ] = ( Dp[ ch[ 1 ] ][ 0 ][ 0 ] + Dp[ ch[ 1 ] ][ 0 ][ 1 ] ) % q ;

  •         } else if ( cnt == 2 ) {

  •                 Dp[ now ][ 0 ][ 1 ] = 0 ;

  •                 Dp[ now ][ 0 ][ 2 ] = ( ll ) ( Dp[ ch[ 1 ] ][ 0 ][ 0 ] + Dp[ ch[ 1 ] ][ 0 ][ 1 ] ) * ( Dp[ ch[ 2 ] ][ 0 ][ 0 ] + Dp[ ch[ 2 ] ][ 0 ][ 1 ] ) % q ;

  •         } else {

  •                 Dp[ now ][ 0 ][ 1 ] = Dp[ now ][ 0 ][ 2 ] = 0 ;

  •         }

  •         rep( i , cnt ) {

  •                 int v = ch[ i ] ;

  •                 sum[ i ][ 0 ][ 0 ] = Dp[ v ][ 0 ][ 0 ] , sum[ i ][ 0 ][ 1 ] = Dp[ v ][ 0 ][ 1 ] , sum[ i ][ 0 ][ 2 ] = Dp[ v ][ 0 ][ 2 ] ;

  •                 REP( j , 1 , ans ) {

  •                         sum[ i ][ j ][ 0 ] = ( sum[ i ][ j - 1 ][ 0 ] + Dp[ v ][ j ][ 0 ] ) % q ;

  •                         sum[ i ][ j ][ 1 ] = ( sum[ i ][ j - 1 ][ 1 ] + Dp[ v ][ j ][ 1 ] ) % q ;

  •                         sum[ i ][ j ][ 2 ] = ( sum[ i ][ j - 1 ][ 2 ] + Dp[ v ][ j ][ 2 ] ) % q ;

  •                 }

  •         }

  •         REP( j , 1 , ans ) {

  •                 g[ 0 ][ 0 ][ 0 ] = g[ 0 ][ 0 ][ 1 ] = g[ 0 ][ 1 ][ 0 ] = g[ 0 ][ 1 ][ 1 ] = g[ 0 ][ 2 ][ 0 ] = g[ 0 ][ 2 ][ 1 ] = 0 ;

  •                 g[ 0 ][ 0 ][ 0 ] = 1 ;

  •                 rep( i , cnt ) {

  •                         int v = ch[ i ] ;

  •                         g[ i ][ 0 ][ 0 ] = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( j - 2 >= 0 ? ( sum[ i ][ j - 2 ][ 0 ] + sum[ i ][ j - 2 ][ 1 ] + sum[ i ][ j - 2 ][ 2 ] ) : 0 ) % q ;

  •                         a = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( Dp[ v ][ j - 1 ][ 0 ] + Dp[ v ][ j - 1 ][ 1 ] + Dp[ v ][ j - 1 ][ 2 ] ) % q ;

  •                         b = ( ll ) g[ i - 1 ][ 0 ][ 1 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] + sum[ i ][ j - 1 ][ 2 ] ) % q ;

  •                         g[ i ][ 0 ][ 1 ] = ( a + b ) % q ;

  •                         a = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] ) % q ;

  •                         b = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( j - 2 >= 0 ? ( sum[ i ][ j - 2 ][ 0 ] + sum[ i ][ j - 2 ][ 1 ] + sum[ i ][ j - 2 ][ 2 ] ) : 0 ) % q ;

  •                         g[ i ][ 1 ][ 0 ] = ( a + b ) % q ;

  •                         a = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( Dp[ v ][ j ][ 0 ] + Dp[ v ][ j ][ 1 ] ) % q ;

  •                         b = ( ll ) g[ i - 1 ][ 0 ][ 1 ] * ( sum[ i ][ j ][ 0 ] + sum[ i ][ j ][ 1 ] ) % q ;

  •                         c = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( Dp[ v ][ j - 1 ][ 0 ] + Dp[ v ][ j - 1 ][ 1 ] + Dp[ v ][ j - 1 ][ 2 ] ) % q ;

  •                         d = ( ll ) g[ i - 1 ][ 1 ][ 1 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] + sum[ i ][ j - 1 ][ 2 ] ) % q ;

  •                         g[ i ][ 1 ][ 1 ] = ( a + b + c + d ) % q ;

  •                         a = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] ) % q ;

  •                         b = ( ll ) g[ i - 1 ][ 2 ][ 0 ] * ( j - 2 >= 0 ? ( sum[ i ][ j - 2 ][ 0 ] + sum[ i ][ j - 2 ][ 1 ] + sum[ i ][ j - 2 ][ 2 ] ) : 0 ) % q ;

  •                         g[ i ][ 2 ][ 0 ] = ( a + b ) % q ;

  •                         a = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( Dp[ v ][ j ][ 0 ] + Dp[ v ][ j ][ 1 ] ) % q ;

  •                         b = ( ll ) g[ i - 1 ][ 1 ][ 1 ] * ( sum[ i ][ j ][ 0 ] + sum[ i ][ j ][ 1 ] ) % q ;

  •                         c = ( ll ) g[ i - 1 ][ 2 ][ 0 ] * ( Dp[ v ][ j - 1 ][ 0 ] + Dp[ v ][ j - 1 ][ 1 ] + Dp[ v ][ j - 1 ][ 2 ] ) % q ;

  •                         d = ( ll ) g[ i - 1 ][ 2 ][ 1 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] + sum[ i ][ j - 1 ][ 2 ] ) % q ;

  •                         g[ i ][ 2 ][ 1 ] = ( a + b + c + d ) % q ;

  •                 }

  •                 Dp[ now ][ j ][ 0 ] = g[ cnt ][ 0 ][ 1 ] ;

  •                 Dp[ now ][ j ][ 1 ] = g[ cnt ][ 1 ][ 1 ] ;

  •                 Dp[ now ][ j ][ 2 ] = g[ cnt ][ 2 ][ 1 ] ;

  •         }

  • }

  •   

  • int main(  ) {

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

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

  •         while ( m -- ) {

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

  •         }

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

  •         dfs( 1 ) ;

  •         rep( i , n ) if ( ! used[ i ] ) {

  •                 printf( "-1\n-1\n" ) ; return 0 ;

  •         }

  •         Dp0( 1 , 0 ) ;

  •         printf( "%d\n" , ans = min( dp[ 1 ][ 0 ] , min( dp[ 1 ][ 1 ] , dp[ 1 ][ 2 ] ) ) ) ;

  •         Dp1( 1 , 0 ) ;

  •         printf( "%d\n" , ( Dp[ 1 ][ ans ][ 0 ] + Dp[ 1 ][ ans ][ 1 ] + Dp[ 1 ][ ans ][ 2 ] ) % q ) ;

  •         return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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