洛谷P4316 绿豆蛙的归宿 题解

题目链接：P4316 绿豆蛙的归宿

题意：

给出张 \(n\) 个点 \(m\) 条边的有向无环图，起点为 \(1\)，终点为 \(n\)，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 \(k\) 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\) 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入格式：

输入的第一行是两个整数，分别代表图的点数 \(n\) 和边数 \(m\)。

第 \(2\) 到第 \((m + 1)\) 行，每行有三个整数 \(u, v, w\)，代表存在一条从 \(u\) 指向 \(v\) 长度为 \(w\) 的有向边。

输出格式：

输出一行一个实数代表答案，四舍五入保留两位小数。

数据范围：

保证 \(1 \leq n \leq 10^5,~1 \leq m \leq 2 \times n,~1 \leq u, v \leq n,~1 \leq w \leq 10^9\)，给出的图无重边和自环。

期望dp经典题。

设 \(f_i\) 表示结点 \(i\) 走到 \(n\) 的期望花费。显然 \(f_n = 0\) 。 考虑转移 \[ f_{u} = \frac{1}{\mathsf{deg}(u)} \times\sum_{(u,v) \in E} \left(f_v + w(u,v)\right) \] 时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define M ((int)(2e5 + 15))

queue<int> q; double f[N];
int n,m,pos=1,head[N],in[N],dg[N];
struct Edge { int u,v,w,next; } e[M];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; ++in[v];}
void topo_sort()
{
    for(q.push(n); !q.empty(); )
    {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            f[v] += (f[u] + e[i].w) / dg[v];
            if(!(--in[v])) q.push(v);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v,w; i<=m; i++)
    {
        cin >> u >> v >> w;
        addEdge(v,u,w); ++dg[u];
    } topo_sort();
    cout << fixed << setprecision(2) << f[1] << '\n';
    return 0;
}

---

今日乐子： \[ \sideset{_7^{10}}{_8^9}{\sideset{_1^4}{_2^3}{f^k_{i,j}}_5^6}_{11}^{12} \]

\sideset{_7^{10}}{_8^9}{\sideset{_1^4}{_2^3}{f^k_{i,j}}_5^6}_{11}^{12}

\(\mathsf{size}(u),~\mathtt{size}(u),~\mathrm{size}(u)\)

\mathsf{size}(u),~\mathtt{size}(u),~\mathrm{size}(u)

感觉 \mathsf 表示函数比 \mathtt 好看