$\text{AcWing}~217$.绿豆蛙的归宿
题目描述
给出一个有向无环的连通图,起点为 $1$,终点为 $N$,每条边都有一个长度。
数据保证从起点出发能够到达图中所有的点,图中所有的点也都能够到达终点。
绿豆蛙从起点出发,走向终点。
到达每一个顶点时,如果有 $K$ 条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 $\frac{1}{K}$。
现在绿豆蛙想知道,从起点走到终点所经过的路径总长度的期望是多少?
思路
一道概率期望 $\text{DP}$ 题。
设 $f_i$ 表示从 $i$ 到 $n$ 的期望路径总长度。初始化 $f_n = 0$,目标求出 $f_1$。
设 $s_1, s_2, …, s_k$ 是 $i$ 能够到达的点,$w_1, w_2, …, w_k$ 分别表示 $i \rightarrow s_1 \sim s_k$ 的路径长度。容易推出方程:$f_i = \sum \limits_{i = 1} ^ j \frac{1}{k} (w_i + f_{s_i})$。
代码实现上,因为是从 $n$ 往回推,所以可以建反图,按拓扑排序的顺序递推即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int din[N], dt[N], q[N];
double f[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void topsort()
{
int hh = 0, tt = -1;
q[ ++ tt] = n;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
f[j] += (f[t] + w[i]) / dt[j];
if ( -- din[j] == 0) q[ ++ tt] = j;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(b, a, c);
din[a] ++ , dt[a] ++ ;
}
topsort();
printf("%.2lf\n", f[1]);
return 0;
}
为什么要倒推呢,正推不行吗(其实真的只能倒推)
正着推
对正着推也可以,就是要维护概率有点麻烦