SHOI 2014 【概率充电器】

时间：2022-05-03 22:20:35

加油，两道了，也就还剩那么二十来道吧，慢慢做。。。。。。

题目大意：

给你一颗树，树上的每一个节点都有一定的概率p[i]能冲上电，有电的点，可以通过树上的边，一定概率地将电传递到与它相邻的点，同时对于每条边，都有一个传递电能的成功率。让你求出通电节点个数的期望。

读入：一个数n，接下来n-1行，每行三个数u，v，p，表示有一条连接节点u和v的边，导电的概率为p，最后一行共n个数，表示每个节点一开始就有电的概率。

  1. 输出：一个数E，表示期望（取6位小数）。

思路分析：

换根DP+期望DP

很清楚，最后的答案就是每一个点通电的概率相加。那么对于每一个点，我们可以求出它不通电的概率，然后再用1去减就可以了。（求不通电的概率比较简单）

有了大致的思路，我们就可以开始设计DP啦！

以1为根，我们开始做树形DP。

对于每一个点u，我们将其分两种情况讨论：

1、以u为根的子树无法使其通上电。

我们建立一个f数组，其中f[u]表示以u为根的子树，无法使u通上电的概率。

那么对于每一个u的儿子v，它不能使u通电又有两种情况：

a、它的儿子v不通电。

b、v通电，但是连接u，v的边不导电。

所以：f[u]=(1-p[u])∏v∈u's son(f[v]+(1-f[v])*(1-P[u,v]))          其中P表示u,v通电的概率

注意：因为a，b两种情况是互斥的两种情况所以f[v]和(1-f[v])*(1-P[u,v])应相加，而对于每一个v无论是哪一个v使u通电都一样，他们是独立的，所以是相乘。

2、u的父亲无法使u通上电。

这种情况，这，这，这——这TM玩个鸡儿啊！！！

万念俱灰，推出了一个看似完美的DP但最终仍是难逃被题目蹂躏的命运。

这第二种情况应该怎么处理呢？怎么处理呢？不会啊，怎么办呢？——不会那就不处理呗！！！

我们都知道，在一棵树中，有一个叫做根节点的神奇玩意儿——它是没有父亲的！

所以再不济，我们以每一个节点为根跑一遍上面的DP不就完事儿了吗！

但是我们真的需要这么做吗？——肯定不用啊！

一遍DP之后得到的大好信息，我们怎么能说扔就扔了呢？浪费可耻啊！

我们建立数组g，其中g[u]为以u为根节点，点u不被充电的概率，显然f[1]=g[1]。

那么我们考虑节点v（v为1号节点的一个儿子），再设一个x为以1为根节点的树，不算儿子v对于1号节点的影响，1号节点不被充电的概率。

那么：g[v]=f[v]*(x+(1-x)*(1-P[1,v]))

而x也很好求，因为对于1号节点的每一个儿子节点，他们对于一号节点的影响都是相对独立的，所以x=g[1]/(f[v]+(1-f[v])*(1-P[1,v]))。

所以整个g数组的转移就被我们推导出来啦！即：g[v]=f[v]*(x+(1-x)*(1-P[u,v]))   其中：x=g[u]/(f[v]+(1-f[v])*(1-P[u,v]))

代码：

var
  next,head,vet:array[1..1000000]of longint;
  vis:array[1..500000]of boolean;
  p,f,dist,g:array[1..1000000]of double;
  tot,i,n,x,y:longint;
  ans,z:double;
procedure add(x,y:longint;z:real);
begin
  inc(tot);
  next[tot]:=head[x];
  vet[tot]:=y;
  head[x]:=tot;
  dist[tot]:=z;
end;
procedure dfs(u:longint);
var
  i,v:longint;
begin
  vis[u]:=true; i:=head[u];
  while i<>0 do
  begin
    v:=vet[i];
    if not vis[v] then
    begin
      dfs(v);
      f[u]:=f[u]*(f[v]+(1-f[v])*(1-dist[i]));
    end;
    i:=next[i];
  end;
end;
procedure change(u:longint);
var
  i,v:longint;
  x:double;
begin
  vis[u]:=true; i:=head[u];
  while i<>0 do
  begin
    v:=vet[i];
    if not vis[v] then
    begin
      x:=g[u]/(f[v]+(1-f[v])*(1-dist[i]));
      g[v]:=f[v]*(x+(1-x)*(1-dist[i]));
      change(v);
    end;
    i:=next[i];
  end;
end;
begin
  read(n);
  for i:=1 to n-1 do
  begin
    read(x,y,z);
    add(x,y,z/100); add(y,x,z/100);
  end;
  for i:=1 to n do
  begin
    read(p[i]);
    p[i]:=p[i]/100;
    f[i]:=1-p[i];
  end;
  dfs(1);
  g[1]:=f[1];
  fillchar(vis,sizeof(vis),false);
  change(1);
  for i:=1 to n do
    ans:=ans+1-g[i];          
  writeln(ans:0:6);
end.

 

标签：

相关文章