概率与期望问题解析：HDU4035

题目链接：HDU 4035

问题描述：存在一个由n个房间构成的迷宫，这些房间通过n-1条隧道相连，形成了一棵无环图。玩家从1号房间开始探索，目标是找到通往外界的出口。在每个房间i中，玩家面临三种选择：

• 被怪物攻击返回起点（概率为ki）
• 发现出口成功逃脱（概率为ei）
• 随机选择一条未探索过的隧道继续前进（假设与当前房间直接相连的隧道总数为m）

目标是计算从起点到成功逃脱所需的平均隧道数。

解决方案：

定义E[i]为从房间i出发达到出口所需的平均隧道数。特别地，E[1]即是我们需要求解的目标值。

对于任意房间i，其E[i]可以通过以下公式计算：

对于叶节点：

E[i] = ki * E[1] + ei * 0 + (1 - ki - ei) * (E[parent[i]] + 1)

对于非叶节点（假设与其相连的隧道数为m）：

E[i] = ki * E[1] + ei * 0 + (1 - ki - ei) / m * (E[parent[i]] + 1 + ∑(E[child[j]] + 1))，其中child[j]表示i的所有子节点。

为了简化上述表达式，我们引入Ai, Bi, Ci来分别表示E[i]中的系数，具体定义如下：

Ai, Bi, Ci分别对应E[1], E[parent[i]], 和常数项的系数。对于每个节点i，我们有：

E[i] = Ai * E[1] + Bi * E[parent[i]] + Ci

进一步推导可以得到：

对于叶节点：

Ai = ki, Bi = 1 - ki - ei, Ci = 1 - ki - ei

对于非叶节点：

Ai = (ki + (1 - ki - ei) / m * ∑Aj) / (1 - (1 - ki - ei) / m * ∑Bj)

Bi = (1 - ki - ei) / m / (1 - (1 - ki - ei) / m * ∑Bj)

Ci = ((1 - ki - ei) + (1 - ki - ei) / m * ∑Cj) / (1 - (1 - ki - ei) / m * ∑Bj)

最终，通过递归计算所有节点的Ai, Bi, Ci值，我们可以求得A1, B1, C1，进而得到E[1] = C1 / (1 - A1)。如果A1接近1，则表明问题无解。

此方法利用了动态规划的思想，有效地解决了问题。值得注意的是，当A1非常接近1时，说明系统几乎无法逃脱，此时应特别注意数值稳定性。