概率最大的路径 (Path with Maximum Probability)

题目描述

给你一个由 $n$ 个节点（下标从 0 开始）组成的无向图，图中包含 $m$ 条无向边。每条边由 (u, v) 表示，并附带一个成功的概率 $p$，表示从节点 $u$ 传播到节点 $v$（或反之）的成功概率。

现在给定起点 start 和终点 end，请找出从 start 到 end 传播成功概率最大的路径，并输出该最大概率。如果不存在从 start 到 end 的路径，请输出 0。

注意：路径的成功概率等于该路径上所有边成功概率的乘积。

---

输入格式

第一行包含两个整数 $n$ 和 $m$，表示节点数和边数。 接下来 $m$ 行，每行包含三个数 $u_i, v_i, p_i$，其中 $u_i, v_i$ 为整数节点编号，$p_i$ 为该边的成功概率（浮点数）。 最后一行包含两个整数 start 和 end。

输出格式

输出一个浮点数，表示最大成功概率。结果保留 6 位小数。

---

输入输出样例

样例 1

输入：

3 3
0 1 0.5
1 2 0.5
0 2 0.2
0 2

输出：

0.250000

解释：0 到 2 有两条路径：0 -> 2 (概率 0.2)；0 -> 1 -> 2 (概率 0.5 * 0.5 = 0.25)。最大概率为 0.25。

样例 2

输入：

3 3
0 1 0.5
1 2 0.5
0 2 0.3
0 2

输出：

0.300000

样例 3

输入：

3 1
0 1 0.5
0 2

输出：

0.000000

---

数据范围与提示

• $2 \le n \le 10,000$
• $0 \le m \le 20,000$
• $0 \le p_i \le 1$
• 每组节点对之间最多有一条边。
• 精度提示：输出结果与标准答案误差在 $10^{-5}$ 以内即可。

---

1. 预备知识点

• 最短路算法（Dijkstra 变体）：本题将“路径和最小”改为“路径乘积最大”。
• 概率乘法原理：路径总概率是各边概率的乘积。
• 对数转换（进阶思考）：$\max(\prod p_i) \Leftrightarrow \max(\sum \log p_i) \Leftrightarrow \min(\sum -\log p_i)$。
• 优先队列（std::priority_queue）：维护当前概率最大的状态。

---

2. 启发式思路引导

第一步：数学建模

在草稿纸上画出样例 1。

• 传统的 Dijkstra 解决的是边权相加的最小化问题。
• 本题是边权相乘的最大化问题。
• 关键性质：因为 $0 \le p_i \le 1$，所以乘积只会越来越小（或保持不变）。这满足贪心选择性质，可以使用类似 Dijkstra 的思路。

第二步：算法迁移

• 状态定义：max_p(i) 表示从起点到节点 $i$ 的最大概率。
• 初始化：max_p(start) = 1.0，其余节点为 0.0。
• 松弛操作：如果通过 $u$ 到达 $v$ 的概率 max_p(u) * p(u,v) 大于当前的 max_p(v)，则更新 max_p(v)。
• 优先级：使用大根堆，每次取出当前已知概率最大的节点进行扩展。

第三步：复杂度分析

• 节点数 $V=10^4$，边数 $E=2 \cdot 10^4$。
• 使用堆优化的 Dijkstra 复杂度为 $O(E \log V)$。
• 空间复杂度为 $O(V + E)$（邻接表存储）。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 初始化概率数组 prob 长度为 n"] --> B["将 prob 数组全部设为 0.0"]
    B --> C["设置 prob(start) 为 1.0"]
    C --> D["建立大根堆 Q, 插入元素 (1.0, start)"]
    D --> E{"堆 Q 是否为空?"}
    E -- "否" --> F["弹出堆顶概率最大的项 (curr_p, u)"]
    F --> G{"curr_p 是否小于当前的 prob(u)?"}
    G -- "是 (失效状态)" --> E
    G -- "否" --> H["遍历 u 的所有邻居 v 以及边概率 p_uv"]
    H --> I["计算通过 u 到达 v 的新概率 next_p 等于 prob(u) 乘以 p_uv"]
    I --> J{"next_p 是否大于当前的 prob(v)?"}
    J -- "是" --> K["更新 prob(v) 为 next_p 并将 (next_p, v) 插入堆 Q"]
    J -- "否" --> H
    K --> H
    H -- "遍历邻居结束" --> E
    E -- "是" --> L["输出 prob(end)"]

---

4. 读题关键词与坑点总结

1. “成功概率的乘积”：这是此题与普通最短路最大的区别。不要习惯性地用 dist[v] = dist[u] + w，而要用 prob[v] = prob[u] * p。
2. “最大概率”：普通 Dijkstra 找最小，这里找最大。优先级队列的比较逻辑需要反过来（C++ 默认 priority_queue 是大根堆，刚好适用）。
3. “无向边”：建图时记得 adj[u].push_back({v, p}) 和 adj[v].push_back({u, p})。
4. 精度问题：处理浮点数建议使用 double。输出时使用 fixed 和 setprecision(6)。
5. 不可达情况：初始值为 0.0，若终点无法到达，最终结果自然是 0.0，符合题意。

---

5. 时间复杂度优化建议

• 堆优化：对于这种稀疏图（$E \approx 2V$），堆优化 Dijkstra 是标配。
• 提前终止：如果在弹出堆顶时发现 u == end，可以直接返回 curr_p，因为 Dijkstra 保证了第一次弹出时即为最大概率。
• 对数转换（防止溢出/常数优化）： 如果概率数值极小（例如经过几百条边），多次相乘可能导致浮点数精度丢失。可以转换成 log。 $\log(a \cdot b) = \log a + \log b$。 因为 $p \le 1$，所以 $\log p \le 0$。我们可以求 $-\log p$ 的最小生成树/最短路。但这题 $n=10^4$ 且 $p$ 范围较好，直接乘法通常是安全的。