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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3566: [SHOI2014]概率充电器(树形DP)  

2014-05-18 21:55:00|  分类: 树形DP,dp,bzoj,o |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


树形DP,设up[ v ]为在v的子树中,v的充电概率,设dp[ v ]为在整颗树中v的充电概率,那么:

令merge( x , y ) = x + y - x * y(容斥原理)

up[ v ] = merge( up[ v ] , up[ child( v ) ] * e( v , child( v ) ) ) 

然后,dp[ root ] = up[ root ],对于一条边(v , u),若v为父亲,dp[ v ]已知,那么dp[ u ]为:

当1 - up[ u ] * e( u , v ) = 0时,dp[ u ] = 1 , 否则 dp[ u ] = merge( up[ u ] , ( dp[ v ] - up[ u ] * e( u , v ) ) / ( 1 - up[ u ] * e( u , v ) ) * e( u , v ) )。


代码:

  • #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 , p ) add( s , t , p ) , add( t , s , p )
  • #define add( s , t , p ) E[ s ].push_back( edge( t , p ) )
  •  
  • const int maxn = 501000 ;
  • const double esp = 0.00000001 ;
  •  
  • struct edge {
  •     int t ;
  •     double p ; 
  •     edge( int _t , double _p ) : t( _t ) , p( _p ) {
  •     }
  • } ;
  • vector < edge > E[ maxn ] ;
  •  
  • int n ; 
  • double q[ maxn ] ;
  •  
  • double up[ maxn ] , dp[ maxn ] ;
  •  
  • double merge( double x , double y ) {
  •     return x + y - x * y ;
  • }
  •  
  • void dfs_up( int now , int fa ) {
  •     up[ now ] = q[ now ] ;
  •     travel( now ) if ( p -> t != fa ) {
  •         dfs_up( p -> t , now ) ;
  •         up[ now ] = merge( up[ now ] , up[ p -> t ] * p -> p ) ;
  •     }
  • }
  •  
  • void dfs_dp( int now , int fa ) {
  •     double rec , ret ; 
  •     travel( now ) if ( p -> t != fa ) {
  •         if ( ( 1 - ( rec = p -> p * up[ p -> t ] ) ) > esp ) {
  •             ret = ( dp[ now ] - rec ) / ( 1 - rec ) ;
  •             dp[ p -> t ] = merge( up[ p -> t ] , ret * p -> p ) ;
  •         } else dp[ p -> t ] = 1.0 ;
  •         dfs_dp( p -> t , now ) ;
  •     }
  • }
  •  
  • int main(  ) {
  •     scanf( "%d" , &n ) ;
  •     rep( i , ( n - 1 ) ) {
  •         int s , t ; double p ; scanf( "%d%d%lf" , &s , &t , &p ) ;
  •         p = p / 100.0 ;
  •         addedge( s , t , p ) ;
  •     }
  •     rep( i , n ) {
  •         scanf( "%lf" , q + i ) ;
  •         q[ i ] = q[ i ] / 100.0 ;
  •     }
  •     dfs_up( 1 , 0 ) ;
  •     dp[ 1 ] = up[ 1 ] ;
  •     dfs_dp( 1 , 0 ) ;
  •     double ans = 0 ;
  •     rep( i , n ) ans += dp[ i ] ;
  •     printf( "%.6f\n" , ans ) ;
  •     return 0 ; 
  • }



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

历史上的今天

评论

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

页脚

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