🧩 问题核心与约束分析

题目给定一个 $N$ 个城市的无向图，其中每条边 $(i, j)$ 有独立的存活概率 $G_{ij}$。我们需要计算：存活下来的边恰好有 $N-1$ 条，并且这些边使得所有城市连通的概率。

关键点：

• 需要形成生成树（恰好 $N-1$ 条边且连通）
• 每条边独立地以概率 $G_{ij}$ 存在
• 需要计算精确到 $N-1$ 条边的概率，而不是通常的"至少连通"

💡 核心思路：变体矩阵树定理

此问题的标准解法是使用矩阵树定理的变体。

🔹 矩阵树定理回顾

经典的矩阵树定理用于计算图中生成树的数量。我们构建拉普拉斯矩阵 $L$：

• 对角元素 $L_{ii} = \sum_{j \neq i} w_{ij}$，其中 $w_{ij}$ 是边 $(i,j)$ 的权重
• 非对角元素 $L_{ij} = -w_{ij}$（如果 $i \neq j$ 且边存在）

那么，生成树的总权重和（即所有生成树的边权重乘积之和）等于 $L$ 的任意 $n-1$ 阶主子式的值。

🔹 应用到概率问题

在概率问题中，如果我们设 $w_{ij} = G_{ij}$（即边的存活概率），那么矩阵树定理计算的是：

$$\sum_{T \text{ 是生成树}} \prod_{(i,j) \in T} G_{ij}$$

但这不是我们想要的答案，因为它包含了所有生成树，但没有考虑非树边不存在的概率。

🔹 调整公式

我们需要的是：对于每棵生成树 $T$，$T$ 中所有边都存在，且不在 $T$ 中的边都不存在的概率。即：

$$\sum_{T \text{ 是生成树}} \left( \prod_{(i,j) \in T} G_{ij} \times \prod_{(u,v) \notin T} (1 - G_{uv}) \right) $$

通过代数变换，可以将其表示为矩阵树定理的形式：

$$\left( \prod_{\text{所有边 } (i,j)} (1 - G_{ij}) \right) \times \sum_{T \text{ 是生成树}} \prod_{(i,j) \in T} \frac{G_{ij}}{1 - G_{ij}} $$

当 $G_{ij} = 1$ 时，公式需调整以避免除零，通常单独处理此类边或设定一个阈值。

🧮 算法实现步骤

步骤说明

1. 计算权重矩阵：

   • 对于所有边 $(i,j)$，计算 $w_{ij} = \frac{G_{ij}}{1 - G_{ij}}$（当 $G_{ij} \neq 1$）
   • 如果 $G_{ij} = 1$，可以使用 $1 - \epsilon$ 近似（如 $\epsilon = 10^{-8}$）

2. 构建拉普拉斯矩阵：

   • $L_{ii} = \sum_{j \neq i} w_{ij}$
   • $L_{ij} = -w_{ij}$（$i \neq j$）

3. 计算行列式：

   • 计算 $L$ 的 $n-1$ 阶主子式的行列式值 $det$

4. 计算最终概率：

   • $P = \left( \prod_{i<j} (1 - G_{ij}) \right) \times det$

⚠️ 数值稳定性考虑

• 当 $G_{ij}$ 接近 $1$ 时，$w_{ij}$ 会很大，可能影响数值稳定性
• 可以使用对数变换或高精度计算来缓解这个问题
• 对于 $G_{ij} = 0$ 的边，可以直接忽略，因为对乘积没有贡献

📊 示例验证

对于样例：

3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0

计算过程：

1. 所有 $1 - G_{ij} = 0.5$，乘积为 $0.5^3 = 0.125$
2. 权重矩阵 $w_{ij} = \frac{0.5}{0.5} = 1$
3. 拉普拉斯矩阵：$$L = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix} $$
4. 任意 $2$ 阶主子式的行列式为 $3$
5. 最终结果：$0.125 \times 3 = 0.375$，与样例输出一致

💎 核心总结

这道题的关键在于：

1. 问题转化：将概率计算问题转化为矩阵树定理可处理的形式
2. 公式调整：通过代数变换处理"恰好 $N-1$ 条边"的条件
3. 数值处理：妥善处理概率为 $0$ 或 $1$ 的边界情况