题解 | #绿豆蛙的归宿#

题目链接

绿豆蛙的归宿

题目描述

给定一个 $N$ 个点、 $M$ 条边的有向无环连通图（DAG）。起点为 $1$ ，终点为 $N$ 。每条边 $(u, v)$ 都有一个非负长度 $w$ 。

当绿豆蛙位于顶点 $u$ 时，如果该点有 $d$ 条出边，它会以等概率（ $1/d$ ）选择其中一条边离开。

请计算绿豆蛙从起点 $1$ 出发，到达终点 $N$ 的路径总长度的期望值。

输入:

第一行输入两个整数 $N, M$ ，分别表示点数与边数。
接下来 $M$ 行，每行输入三个整数 $u, v, w$ ，表示存在一条从 $u$ 指向 $v$ 、长度为 $w$ 的有向边。
保证图是 DAG，且从 $1$ 可以到达 $N$ 。

输出:

输出一个实数，表示期望路径长度，四舍五入保留两位小数。

解题思路

这是一个在有向无环图（DAG）上求期望的经典问题，可以使用动态规划（或记忆化搜索）来解决。

1. 定义状态

我们要求的是从起点 $1$ 到终点 $N$ 的期望路径长度。
一个很自然的想法是定义 dp[u] 表示从起点 $1$ 到达点 $u$ 的期望路径长度。但是这个状态很难转移，因为一个点 $u$ 可能有多个前驱节点，计算 $u$ 的期望需要综合考虑所有到达它的路径及其概率，非常复杂。
更巧妙的方法是反向定义状态。设 dp[u] 为从点 $u$ 出发到达终点 $N$ 所需要的期望路径长度。我们的目标就是求 dp[1]。

2. 状态转移方程

基本情况：对于终点 $N$ ，它已经到达了归宿，所以从 $N$ 出发到 $N$ 的期望长度为 $0$ 。即 dp[N] = 0。
递推关系：对于任意一个非终点 u，考虑它下一步的走向。
- 设点 $u$ 有 $d_u$ 条出边，分别通向 $v_1, v_2, \dots, v_{d_u}$ ，对应的边长为 $w_1, w_2, \dots, w_{d_u}$ 。
- 根据题意，绿豆蛙会以 $1/d_u$ 的概率选择任意一条出边 $(u, v_j)$ 。
- 如果选择了边 $(u, v_j)$ ，那么从 $u$ 出发的总路径长度，就是这条边的长度 $w_j$ 加上从 $v_j$ 再走到终点 $N$ 的期望长度 dp[v_j]。
- 根据全期望公式，从 $u$ 出发的总期望长度，就是所有可能选择的期望长度的加权平均： $dp[u] = \sum_{j=1}^{d_u} P(\text{选择边 } (u,v_j)) \cdot (w_j + dp[v_j])$ $dp[u] = \sum_{j=1}^{d_u} \frac{1}{d_u} \cdot (w_j + dp[v_j])$ $dp[u] = \frac{1}{d_u} \left( \sum_{j=1}^{d_u} (w_j + dp[v_j]) \right)$

3. 计算顺序

观察状态转移方程，我们发现要计算 dp[u]，必须先知道它所有后继节点 $v_j$ 的 dp 值。
在一个 DAG 中，所有节点的后继节点的拓扑序都在该节点之后。因此，我们需要按照拓扑序的逆序来进行计算。
实现上，最简洁的方式是使用记忆化搜索（DFS）。我们从 dfs(1) 开始调用，函数会递归地深入到图的末端，当遇到终点 $N$ 时返回 $0$ 。在回溯的过程中，每个节点的 dp 值都会被计算并存储起来，避免重复计算。

4. 算法流程

读入图，并使用邻接表存储。同时，计算每个节点的出度。
定义 dp 数组用于记忆化，初始化为一个特殊值（例如 -1）。
编写 dfs(u) 函数：
- 如果 dp[u] 已经被计算过，直接返回。
- 如果 u == N，返回 0。
- 初始化 sum = 0。
- 遍历 u 的所有出边 $(u, v, w)$ ，对每一条边，sum += w + dfs(v)。
- 计算 dp[u] = sum / out_degree[u]。
- 返回 dp[u]。
调用 dfs(1) 并输出结果。

代码

c++
java
python

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

using namespace std;

int n, m;
vector<pair<int, int>> adj[100005];
int out_degree[100005];
double dp[100005];
bool visited[100005];

double solve(int u) {
    if (visited[u]) {
        return dp[u];
    }
    if (u == n) {
        return 0.0;
    }
    
    visited[u] = true;
    double expected_len = 0.0;
    
    for (auto const& [v, w] : adj[u]) {
        expected_len += (double)w + solve(v);
    }
    
    dp[u] = expected_len / out_degree[u];
    return dp[u];
}

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

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        out_degree[u]++;
    }

    double result = solve(1);

    cout << fixed << setprecision(2) << result << endl;

    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static List<List<int[]>> adj;
    static int[] outDegree;
    static double[] dp;
    static boolean[] visited;

    public static double solve(int u) {
        if (visited[u]) {
            return dp[u];
        }
        if (u == n) {
            return 0.0;
        }

        visited[u] = true;
        double expectedLen = 0.0;

        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            int w = edge[1];
            expectedLen += (double)w + solve(v);
        }
        
        dp[u] = expectedLen / outDegree[u];
        return dp[u];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        outDegree = new int[n + 1];
        dp = new double[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adj.get(u).add(new int[]{v, w});
            outDegree[u]++;
        }

        double result = solve(1);
        System.out.printf("%.2f\n", result);
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(100005)

def solve(u):
    # 如果已经计算过，直接返回
    if visited[u]:
        return dp[u]
    
    # 到达终点，期望为0
    if u == n:
        return 0.0

    visited[u] = True
    expected_len = 0.0
    
    # 遍历所有出边
    for v, w in adj[u]:
        expected_len += w + solve(v)
    
    # 计算期望
    dp[u] = expected_len / out_degree[u]
    return dp[u]

def main():
    global n, adj, out_degree, dp, visited
    
    n, m = map(int, input().split())
    
    adj = [[] for _ in range(n + 1)]
    out_degree = [0] * (n + 1)
    dp = [0.0] * (n + 1)
    visited = [False] * (n + 1)

    for _ in range(m):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))
        out_degree[u] += 1
        
    result = solve(1)
    print(f"{result:.2f}")

if __name__ == "__main__":
    main()

算法及复杂度

算法：期望动态规划 / 记忆化搜索
时间复杂度：每个点和每条边都只会被访问一次。因此，总时间复杂度为 $\mathcal{O}(N+M)$ 。
空间复杂度：需要邻接表来存储图，以及 DP 数组和出度数组，空间复杂度为 $\mathcal{O}(N+M)$ 。