P4284 [SHOI2014]概率充电器

    • 421通过
    • 950提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 期望 条件概率 连通块 高斯消元 各省省选 2014 上海 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    著名的电子产品品牌SHOI 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器:

    “采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决 定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看 吧!”

    SHOI 概率充电器由n-1 条导线连通了n 个充电元件。进行充电时,每条导 线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率 决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行 间接充电。

    作为SHOI 公司的忠实客户,你无法抑制自己购买SHOI 产品的冲动。在排 了一个星期的长队之后终于入手了最新型号的SHOI 概率充电器。你迫不及待 地将SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件 个数的期望是多少呢?

    输入输出格式

    输入格式:

    第一行一个整数:n。概率充电器的充电元件个数。充电元件由1-n 编号。

    之后的n-1 行每行三个整数a, b, p,描述了一根导线连接了编号为a 和b 的 充电元件,通电概率为p%。

    第n+2 行n 个整数:qi。表示i 号元件直接充电的概率为qi%。

    输出格式:

    输出一行一个实数,为能进入充电状态的元件个数的期望,四舍五入到小 数点后6 位小数。

    输入输出样例

    输入样例#1: 复制
    3
    1 2 50
    1 3 50
    50 0 0
    输出样例#1: 复制
    1.000000
    输入样例#2: 复制
    5
    1 2 90
    1 3 80
    1 4 70
    1 5 60
    100 10 20 30 40
    输出样例#2: 复制
    4.300000

    说明

    对于30%的数据,n≤5000。

    对于100%的数据,n≤500000,0≤p,qi≤100。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。