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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2878: [Noi2012]迷失游乐园(树,环DP)  

2014-05-15 20:32:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

 

在树上维护两个东西up(v),down(v),表示向上和向下的期望长度,n=m的话就把环搞出来,弄成个环套树,然后DP即可。

 

代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  •   

  • using namespace std ;

  •   

  • #define travel( x ) for ( vector < edge > :: iterator p = E[ x ].begin(  ) ; p != E[ x ].end(  ) ; ++ p )

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

  •   

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

  • #define add( s , t , d ) E[ s ].push_back( edge( t , d ) )

  •   

  • const int maxn = 100100 ;

  •   

  • struct edge {

  •     int t , d ; 

  •     edge( int _t , int _d ) : t( _t ) , d( _d ) {

  •     }

  • } ;

  • vector < edge > E[ maxn ] ;

  •   

  • double sum[ maxn ] , down[ maxn ] , up[ maxn ] , cnt[ maxn ] , d[ maxn ] ;

  • bool used[ maxn ] ;

  •   

  • void dp_down( int now , int fa ) {

  •     cnt[ now ] = sum[ now ] = 0 ; 

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

  •         cnt[ now ] += 1 ; 

  •         dp_down( p -> t , now ) ;

  •         sum[ now ] += double( p -> d ) + down[ p -> t ] ;

  •     }

  •     if ( cnt[ now ] ) down[ now ] = sum[ now ] / cnt[ now ] ;

  • }

  •   

  • void dp_up( int now , int fa ) {

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

  •         if ( d[ now ] > 1.000001 ) up[ p -> t ] = double( p -> d ) + ( sum[ now ] - double( p -> d ) - down[ p -> t ] + up[ now ] ) / ( d[ now ] - 1 ) ; else up[ p -> t ] = double( p -> d ) + up[ now ] ;

  •         dp_up( p -> t , now ) ;

  •     }

  • }

  •   

  • int n , m ; 

  •   

  • double solve0(  ) {

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

  •     dp_down( 1 , 0 ) ;

  •     dp_up( 1 , 0 ) ;

  •     double ans = 0 ; 

  •     rep( i , n ) ans += ( sum[ i ] + up[ i ] ) / d[ i ] ;

  •     return ans / double( n ) ;

  • }

  •   

  • bool flag = false ;

  • int Stack[ maxn ] , Cnt = 0 , len , node[ maxn ] ;

  • double D[ maxn ] , dist[ maxn ] ;

  •   

  • void dfs( int now , int fa ) {

  •     if ( flag ) return ; 

  •     used[ now ] = true , Stack[ Cnt ++ ] = now ;

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

  •         if ( flag ) return ; 

  •         int i ;

  •         for ( i = 0 ; i < Cnt && Stack[ i ] != p -> t ; ++ i ) ;

  •         len = 0 ; 

  •         for ( ; i < Cnt ; ++ i ) {

  •             node[ len ] = Stack[ i ] ;

  •             dist[ len ++ ] = D[ i ] ;

  •         }

  •         dist[ len - 1 ] = double( p -> d ) ;

  •         flag = true ;

  •         return ; 

  •     } else {

  •         D[ Cnt - 1 ] = double( p -> d ) ;

  •         dfs( p -> t , now ) ;

  •     }

  •     used[ now ] = false , -- Cnt ;

  • }

  •   

  • double left[ maxn ] , right[ maxn ] ;

  •   

  • double solve1(  ) {

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

  •     dfs( 1 , 0 ) ;

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

  •     for ( int i = 0 ; i < len ; ++ i ) used[ node[ i ] ] = true ;

  •     for ( int i = 0 ; i < len ; ++ i ) dp_down( node[ i ] , 0 ) ;

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

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

  •     for ( int i = 0 ; i < len ; ++ i ) {

  •         left[ i ] = right[ i ] = 0 ; 

  •         for ( int p = i , j = ( i + 1 ) % len ; j != i ; ( j += 1 ) %= len , ( p += 1 ) %= len ) {

  •             if ( d[ node[ p ] ] < 2.01 || p != i ) left[ j ] = dist[ p ] + ( ( left[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 1 ) ) ;

  •             else left[ j ] = dist[ p ] + ( ( left[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 2 ) ) ;

  •         }

  •         for ( int p = i , j = ( i - 1 + len ) % len ; j != i ; j = ( j - 1 + len ) % len , p = ( p - 1 + len ) % len ) {

  •             if ( d[ node[ p ] ] < 2.01 || p != i ) right[ j ] = dist[ j ] + ( right[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 1 ) ;

  •             else right[ j ] = dist[ j ] + ( right[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 2 ) ;

  •         }

  •         up[ node[ ( i - 1 + len ) % len ] ] += left[ ( i - 1 + len ) % len ] ;

  •         up[ node[ ( i + 1 ) % len ] ] += right[ ( i + 1 ) % len ] ;

  •     }

  •     for ( int i = 0 ; i < len ; ++ i ) dp_up( node[ i ] , 0 ) ;

  •     double ans = 0 ; 

  •     for ( int i = 0 ; i ++ < n ; ) ans += ( up[ i ] + sum[ i ] ) / d[ i ] ;

  •     return ans / double( n ) ;

  • }

  •   

  • int main(  ) {

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

  •     rep( i , m ) {

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

  •         d[ s ] += 1, d[ t ] += 1 , addedge( s , t , w ) ;

  •     }

  •     if ( m == n - 1 ) printf( "%.5f\n" , solve0(  ) ) ; else printf( "%.5f\n" , solve1(  ) ) ;

  •     return 0 ;

  • }

 

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

历史上的今天

评论

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

页脚

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