[SHOI2014]概率充电器 (概率dp)

题意:

著名的电子产品品牌 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%。

输出格式:

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

数据范围与提示

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

分析:

一看到概率就知道这是一道概率树上dp,一开始发现毫无头绪,这个怎么算….每个点和每一条边都有概率…..(GG,跳过好了)
但是我们可以发现,对于一个点来说,他要么自己亮要么被点亮,怎么算呢?我们发现直接算简直药丸,我反正不会写….那么我们考虑倒着找,一个点不被点亮是什么情况,首先他自己不亮,其次他不被相邻点点亮…..(我不会告诉你我看了一下题解,虽然只有数组定义,但是给了我很大启发).
我们设f[i]表示i点不被他的儿子点亮的概率(我设1为根),设g[i]为一个点不被他的父亲点亮的概率….
那么我们考虑怎么转移:
假设我们现在在i点,那么把son[i]存了他的儿子们
假设连向儿子的边是edge.
那么首先考虑如果一条连向儿子的边根本不联通,概率是1-edge_p,然后我们考虑这条边联通,那么这个儿子本身不能亮,同时不被儿子的儿子们点亮,可以轻易写出edge_p \ast(1-q_{son})\ast f[son] ,总的来说,有:

f[i]=\prod\limits_{son_i\in son[i] } \Big ( (1 – edge_p) + edge_p\ast (1 – q_{son} \ast f[son] )\Big )

然后我们来考虑不被父亲点亮的概率,同理首先有1-edge_p,然后我们考虑这条边联通但是父亲没有亮的情况,易得

edge_p \ast (1-q_fa) \ast g[fa] \ast f[fa] / \Big( (1-edge_p)+edge_p\ast (1-q_i) \Big)

合起来就是:

g[i]=(1-edge_p)+edge_p \ast (1-q_fa) \ast g[fa] \ast f[fa] / \Big( (1-edge_p)+edge_p\ast (1-q_i) \Big)

然后我们写两遍树型dp就好了…

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e5+10;
const LL inf=0x3f3f3f3f;
const LL mod=1e9+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n;
int head[N],cnt;
struct Edge{int next,to;double p;}edge[N*2];
inline void add(int from,int to,int p)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].p=(double)1.0*p/100.0;
    head[from]=cnt;
}
double xx[N],f[N],g[N],ans;
int fa[N];
void dfs_F(int now,int fath)
{
    f[now]=1;fa[now]=fath;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fath) continue;
        dfs_F(to,now);
        f[now]*=(double)(1-edge[i].p)+1.0*edge[i].p*(1-xx[to])*f[to];
    }
}
void dfs_G(int now)
{
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa[now]) continue;
        g[to]=(double)(1.0-edge[i].p)+edge[i].p*(1.0-xx[now])*g[now]*f[now]/((1-edge[i].p)+edge[i].p*(1.0-xx[to])*f[to]);
        dfs_G(to);
    }
}
signed main()
{
    read(n);
    for(int i=1;i<n;i++)
    {
        int u,v,p;
        read(u),read(v),read(p);
        add(u,v,p),add(v,u,p);
    }
    for(int i=1,u;i<=n;i++) read(u),xx[i]=(double)u/100.0;
    dfs_F(1,0);g[1]=1;dfs_G(1);
    for(int i=1;i<=n;i++)
        ans+=1.0-g[i]*f[i]*(1-xx[i]);
    printf("%.6lf\n",ans);
    return 0;
}

关于“[SHOI2014]概率充电器 (概率dp)”我的2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注