[Leaf] [P4316] 绿豆蛙的归宿

p4316-绿豆蛙的归宿---洛谷">P4316 绿豆蛙的归宿 - 洛谷

1. 题面梗概

中译中：给出一个 $n$ 个点 $m$ 条边的 DAG。从点 1 出发，每到一个点 $u$，等概率选择其出边中的一条走向下一个点。求到达点 $n$ 时经过的路径总长度的期望值。

$1 \le n \le 10^5, 1 \le m \le 2n$

2. 逻辑推导

这显然是个 期望DP 题，如果正向推导 $(1 \to u)$ ，我们需要处理 “到达 $u$ 的概率” 和 “到达点 $u$ 的期望路径长”，逻辑比较混乱。

不妨定义：$f[u]$ 为从点 $u$ 出发到终点 $n$ 的期望路径长度。

显然，终点 $f[n] = 0$，我们要求的是 $f[1]$。

2.1 全概率公式

假设点 $u$ 有 $k$ 条出边，分别指向 $v_{1}, v_{2}, \dots, v_{k}$，边权分别为 $w_{1}, w_{2}, \dots, w_{k}$。

按照期望的定义，从 $u$ 出发的期望等于走向各个分支的概率乘以其分支后的期望。

$$f[u] = \sum_{i=1}^{k} \frac{1}{k} \times ( f[v_{i}] + w_{i} )$$

每条边被选中的概率都是 $\frac{1}{k}$，一旦选中了边 $(u, v_{i})$，我们就先走过了 $w_{i}$ 的距离，剩下的期望距离就是 $f[v_{i}]$。

2.2 拓扑序

由于图是 DAG，我们可以利用拓扑排序来确保计算 $f[u]$ 时，其所有的后继节点 $v_{i}$ 的 $f[v_{i}]$ 已经计算完成。

所以反着建图，跑一遍拓扑序 DP 就行。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5 + 5;

struct Edge { int v, w; };
vector< Edge > radj[maxn];
double f[maxn];
// u -> n 的期望路径长度
int outdeg[maxn]; // 期望用 deg
int deg[maxn]; // 拓扑用 deg
int n, m;

int main( )
{
    cin >> n >> m;
	
    for( int i = 1; i <= m; ++ i )
    {
        int u, v, w;
        cin >> u >> v >> w;
        radj[v].push_back({ u, w });
        outdeg[u] ++;
        deg[u] ++;
    }
	
    queue< int > q;
    f[n] = 0; q.push( n );
    
    while( !q.empty( ) )
    {
        int v = q.front( ); q.pop( );
        for( auto [u, w] : radj[v] )
        {
            f[u] += ( f[v] + w ) / outdeg[u];
            deg[u] --;
            if( deg[u] == 0 ) q.push( u );
        }
    }
	
    cout << setprecision(2) << fixed << f[1] << '\n';
    return 0;
}

4. 复盘

• 复杂度分析：$O( n + m )$。

• 碎碎念：期望DP，反着按拓扑序递推。

关联笔记：树图DP | 拓扑排序