题解 | #绿豆蛙的归宿#

问题分析

本题的核心在于求解有向无环图（DAG）上的期望路径长度。由于图的结构是 DAG，其天然具备偏序关系，这使得我们可以通过动态规划（DP）或递推的方式解决问题。

关键性质：

1. 无环性（DAG）： 保证了状态转移不会出现环路依赖，可以使用拓扑排序或递归记忆化搜索。
2. 期望的线性性质： 期望值 具有加法特性。对于节点 到终点 的期望距离，等于其所有后继节点 到 的期望距离的加权平均值，再加上当前边的贡献。
3. 等概率选择： 若节点 的出度为 ，则每条出边的概率权值为 。这意味着我们需要预先统计每个节点的出度。

算法：期望 DP

在处理期望问题时，通常有两种状态定义方向：顺推（从起点出发）和逆推（从终点出发）。

1. 为什么选择“逆推”？

如果我们定义 为从起点 到节点 的期望距离，计算时需要同时维护“到达 的概率”和“到达 的期望路径长”，逻辑相对复杂。 反之，如果我们定义 为从节点 到终点 的期望路径长度，则：

• 目标状态： 即为所求。
• 边界状态： （终点到终点的期望距离为 0）。
• 转移方程： 设节点 有 条出边，分别指向 ，边权分别为 ，则： 整理得：

2. 图的遍历策略

由于状态 依赖于其后继节点 ，我们需要按照 拓扑序列的逆序 进行计算。最直接的实现方式有两种：

• 反向拓扑排序： 建立反向图，从终点 开始进行拓扑排序，或者在原图上通过入度为 0 的点（终点视角）进行递推。
• 记忆化搜索（DFS）： 从起点 开始递归探测，利用递归栈的特性，在回溯时计算期望值。这种方式逻辑最简洁，不需要显式构建反向图。

复杂度分析

• 时间复杂度：
• 空间复杂度：

代码实现

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pii>> rev_adj(n + 1);
    vector<int> out_deg(n + 1, 0);
    vector<double> E(n + 1, 0.0);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        rev_adj[b].push_back({a, c});
        out_deg[a]++;
    }

    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (out_deg[i] == 0)
            Q.push(i);
    }
    E[n] = 0.0;

    vector<int> cnt = out_deg;
    while (!Q.empty()) {
        auto v = Q.front();
        Q.pop();

        for (const auto& [u, w] : rev_adj[v]) {
            E[u] += (E[v] + w) / cnt[u];

            if (--out_deg[u] == 0) {
                Q.push(u);
            }
        }
    }

    cout << fixed << setprecision(2) << E[1] << endl;
}