绿豆蛙的归宿

形式化题目

给定一个包含 $n$ 个节点和 $m$ 条有向边的加权有向无环图 $G = (V, E, w)$ ，起点为 $1$ ，终点为 $n$ 。保证从 $1$ 出发可达所有节点，所有节点均可到达 $n$ 。一个随机游走过程从点 $1$ 出发：若当前位于节点 $u$ （ $u \neq n$ ），设其出度为 $k_u = |\text{succ}(u)|$ ，则以等概率 $\frac{1}{k_u}$ 随机选择一条出边 $(u, v)$ 转移到后继节点 $v$ 。当首次到达节点 $n$ 时游走终止。求从起点 $1$ 游走到终点 $n$ 所经过的有向边权值之和的数学期望 $\mathbb{E}[L]$ 。

暴力解法

思路

根据离散型随机变量数学期望的原始定义：

\mathbb{E}[L] = \sum_{P: 1 \rightsquigarrow n} \Pr(P) \cdot \text{len}(P)

其中

P

为任意一条从

1

到

n

的简单有向路径。若路径由序列

v_0=1, v_1, \dots, v_k=n

构成，则该路径产生的概率为沿途各节点出边分支概率的乘积：

\Pr(P) = \prod_{i=0}^{k-1} \frac{1}{\text{out\_deg}(v_i)}

其路径总长为沿途边权之和

\text{len}(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})

。我们可以通过深度优先搜索枚举所有从

1

出发到达

n

的简单路径，在递归遍历中维护当前到达的节点、当前路径的累积概率与累积长度。当到达终点

n

时，将概率与长度的乘积计入总期望。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * brute.cpp：基于期望离散定义的全路径枚举暴力解法
 * 
 * 为什么只适合小数据：
 * 本解法采用深度优先搜索，枚举所有从起点 1 到终点 n 的合法走法（简单路径）。
 * 在最坏情况下（例如完全分层 DAG），两点间的简单路径数量随节点数呈指数级爆炸（O(2^n)）。
 * 当 n 超过 20~30 时，递归搜索所有路径会引发严重的运行超时（TLE）。
 * 该暴力仅用于小规模数据下验证数学定义的正确性，并作为对拍的基准。
 * 
 * 浮点精度说明：
 * 采用 long double 进行高精度概率和路径长度累加，尽量减少中间阶段的大量乘除截断误差。
 */

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

typedef long long ll;

const int maxn = 100005;

struct Edge {
    int to;
    ll w;
};

int n, m;
vector<Edge> g[maxn];
int out_deg[maxn];

long double total_expected_len = 0.0;

// dfs 搜索所有从 1 到 n 的完整路径，累加路径概率与长度之积
void dfs(int u, long double curr_prob, long double curr_len) {
    if (u == n) {
        total_expected_len += curr_prob * curr_len;
        return;
    }
    
    for (const auto &e : g[u]) {
        long double next_prob = curr_prob / (long double)out_deg[u];
        dfs(e.to, next_prob, curr_len + (long double)e.w);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n >> m)) return 0;
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        out_deg[u]++;
    }
    
    dfs(1, 1.0L, 0.0L);
    
    cout << fixed << setprecision(2) << (double)total_expected_len << "\n";
    
    return 0;
}

复杂度

时间复杂度： $O(\text{简单路径总数})$ 。在最坏的有向无环图中，两点之间的简单路径数量随节点规模呈指数级增长，可达 $O(2^n)$ 甚至更高。
空间复杂度： $O(n)$ ，为递归调用栈所占用的深度。

瓶颈

暴力枚举的做法独立考虑了每一条路径，但在 DAG 中，大量不同的路径在经过相同中间节点 $u$ 后，后续走向终点 $n$ 的随机过程具有完全相同的概率结构。暴力重复遍历了这些公共后缀，导致计算量随路径数指数级膨胀，无法承受 $n = 10^5$ 的数据规模。

正解

思路

为了消除重复计算，我们需要利用有向无环图的无后效性，通过动态规划将公共后缀合并。

为什么逆向设状态？

在马尔可夫决策或随机游走中，如果正向定义状态（如“从起点到节点 $u$ 的期望距离”），由于到达节点 $u$ 的各条路径概率各不相同，汇合到 $u$ 时需要考虑条件概率加权，状态推导较为繁琐。而如果逆向设状态：设 $f(u)$ 表示从节点 $u$ 出发走到终点 $n$ 所需走过的路径总长度的数学期望。根据马尔可夫性质，绿豆蛙从节点 $u$ 出发走向后继节点 $v$ 的分支概率只与节点 $u$ 的出度有关，与此前“是如何走到 $u$ 的”完全无关。

全期望公式转移

由全期望公式，在节点 $u$ （ $u \neq n$ ）：

f(u) = \sum_{(u, v) \in E} \Pr(u \to v) \cdot \Big( f(v) + w(u, v) \Big)

由于题目规定以等概率

\frac{1}{\text{out\_deg}(u)}

走向每条出边，因此：

f(u) = \frac{1}{\text{out\_deg}(u)} \sum_{(u, v) \in E} \Big( f(v) + w(u, v) \Big)

边界条件： $f(n) = 0$ （到达终点后不再移动，剩余期望长度为 0）。
目标答案： $f(1)$ 。

拓扑序与记忆化搜索

由于图为有向无环图，转移依赖关系天然构成拓扑序。我们可以直接使用记忆化搜索实现：

从起点 dfs(1) 开始递归；
若已访问过节点 $u$ （vis[u] == true），直接返回记录的值 $f[u]$ ；
否则遍历 $u$ 的所有出边 $(u, v)$ ，递归计算后继 $v$ 的期望，按公式累加并除以出度；
递归天然按照逆拓扑序求值，代码极其简明，且自动跳过了与 $1 \rightsquigarrow n$ 无关的节点。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

typedef long long ll;

const int maxn = 100005;

struct Edge {
    int to;
    ll w;
};

int n, m;
vector<Edge> g[maxn];
int out_deg[maxn];
double f[maxn];
bool vis[maxn];

// dfs(u) 计算从节点 u 出发到达终点 n 的期望路径长度
double dfs(int u) {
    if (u == n) {
        return 0.0;
    }
    if (vis[u]) {
        return f[u];
    }
    vis[u] = true;
    
    double sum = 0.0;
    for (const auto &e : g[u]) {
        sum += (dfs(e.to) + (double)e.w);
    }
    
    // 全期望公式：以 1/out_deg[u] 的等概率走向每个后继节点
    f[u] = sum / (double)out_deg[u];
    return f[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n >> m)) return 0;
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        out_deg[u]++;
    }
    
    cout << fixed << setprecision(2) << dfs(1) << "\n";
    
    return 0;
}

复杂度

时间复杂度： $O(n + m)$ 。记忆化搜索保证每个节点 $u$ 只被计算一次，每条有向边 $(u, v)$ 恰好被遍历一次。对于 $n \le 10^5, m \le 2 \times 10^5$ ，总运算次数在 $3 \times 10^5$ 左右，实测耗时在 20ms 以内。
空间复杂度： $O(n + m)$ 。邻接表存图占用 $O(m)$ 空间，记忆化数组与访问标记占用 $O(n)$ 空间；递归栈在最坏的长链图下深度为 $n$ ，占用内存约 3.2MiB，在常规评测限制下非常安全。

总结

本题是典型的有向无环图（DAG）上的期望动态规划模型。通过将正向概率加权转化为“从当前节点出发到达终点的剩余期望”这一逆向状态定义，完美利用了马尔可夫无后效性，规避了条件概率的复杂推导。配合记忆化搜索，既直观对应全期望公式，又天然契合 DAG 的拓扑转移顺序。

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

为什么逆向设状态？

全期望公式转移

拓扑序与记忆化搜索

代码

复杂度

总结