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

 
 
 

日志

 
 

HNOI 2013 Day2 游走 ( BZOJ 3143 ) 无向图的点与边的期望问题+高斯消元  

2014-01-29 09:55:08|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先表示 Foreseeable 的讲解很详细
然后我大概整理了一下
-------------------------------------------------------------------------------------------
边的期望不方便直接求
如果我们求出了点的期望次数
就可以靠算贡献的办法求出边走过的期望次数
对于uv的边
从u->v这条路线被走过的期望次数就是Eu/Du
从v->u这条路线被走过的期望次数就是Ev/Dv
所以边uv被走过的期望次数就是Eu/Du+Ev/Dv
-------------------------------------------------------------------------------------------
而对于每个点的期望
 Ev=Σ(存在边i->v)Ei/Di
此处对于重边自环什么的也是可以的
(详见HNOI 2011 xor)
不过题目中有 无向“简单”连通图 的说明
即无重边自环 所以也不用考虑
-------------------------------------------------------------------------------------------
最后就是高斯消元的部分
即使没学过行列式
直接模拟也是可以的
但要记住每次找绝对值最大的来消元
-------------------------------------------------------------------------------------------
在BZOJ上此题是有spj的 所以精度差别不算太大就不用担心
  评论这张
 
阅读(149)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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