分析
-
本题可以看成一个动态规划的题目。
-
我们使用
f(i)
表示从i
跳到N
的期望长度,边界f(N)=0
。最终我们的答案就是f(1)
。考虑从i
有k
条出边,如下图:
- 则事件
X
满足下式:
$$ X = \frac{1}{k} (w_1 + X_1) + \frac{1}{k} (w_2 + X_2) + … + \frac{1}{k} (w_k + X_k) $$
- 两边同时求期望可得:
$$ EX = E \big(\frac{1}{k} (w_1 + X_1) + \frac{1}{k} (w_2 + X_2) + … + \frac{1}{k} (w_k + X_k)\big) \\\\ = \frac{1}{k} (w_1 + EX_1) + \frac{1}{k} (w_2 + EX_2) + … + \frac{1}{k} (w_k + EX_k) $$
- 因为
f(i)=EX
,因此有:
$$ f(i) = \frac{1}{k} (w_1 + f(S_1)) + \frac{1}{k} (w_2 + f(S_2)) + … + \frac{1}{k} (w_k + f(S_k)) $$
- 我们可以使用记忆化搜索求解该问题。
代码
- C++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dout[N]; // 每个点的出度
double f[N]; // 记录每个点到N的期望长度
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
double dp(int u) {
if (f[u] > 0) return f[u];
f[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
f[u] += (w[i] + dp(j)) / dout[u];
}
return f[u];
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
dout[a]++;
}
memset(f, -1, sizeof f);
printf("%.2lf", dp(1));
return 0;
}