题意分析:
据说这还是一道板子题.....是期望dp的板子题…还是自己太辣鸡,开提高课已经急不可待了
updata:8/19
我是笨比,高中概率统计学了个什么勾八,想了这么长时间才想明白......首先明白一点:
到达某个结果的期望值 = 这个结果 * 从起始状态到这个状态的概率
什么意思呢?
如图:
我们计算从1号点到3号点的期望距离:
$$ 路径1. 1 - > 3: E_1 = 2 \times \frac{1}{2} = 1 \\\ 路径2. 1 -> 2 -> 3 :E_2 = 1 \times \frac{1}{2} + 3 \times \frac{1}{2} = 2 \\\这里路径2中从1到2概率为 \frac{1}{2} ,但单看从2到3概率就是1, \\\但是从1到3那就是从(1到2的概率) \frac{1}{2} \times 1(2到3的概率) = \frac{1}{2}。 \\ 总结:概率是要叠乘的 $$
这题是有正推和倒推两种写法的。
知道上面的东西之后那么我们就可以来搞正推的写法了
正推:
设:a1, a2, a3 … ak 到 j 的权值为 w1, w2, w3 … wk,
从起点到这k个点的概率为:p1, p2, p3 … pk
每个点的出度为:out1, out2, out3, … , outk
==注==:这里的1~k个点的从起点的到该点的概率一定是确定的也就是说这个点的概率是被更新完的,即此时这个点的入度为0!
那么就有:
$$
E(i):表示从起点到i点的期望距离
\\\ E(J) = \frac{E(1) +w_1\times p_1}{out_1} + \frac{E(2) +w_2 \times p_2}{out_2}
\\\ +\frac{E(3) +w_3\times p_3}{out_3} + … +\frac{E(k) +w_k\times p_k}{out_k}
\\\ =\sum_{i=1}^{k}{ \frac{E(i) +w_i\times p_i}{out_i}}
$$
以上即是正推的递推式
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int n, m;
int out[N], in[N];
double f[N], p[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
double topsort()
{
queue<int> q;
for(int i = 1; i <= n; i++)
if(!in[i]) q.push(i), p[i] = 1;
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
f[j] += (w[i] * p[t] + f[t]) * 1.0 / out[t] ;
p[j] += p[t] * 1.0 / out[t];
in[j]--;
if(!in[j]) q.push(j);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) h[i] = -1;
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
out[a]++, in[b]++;
}
topsort();
// for(int i = 1; i <= n; i++)
// printf("%d--%.2lf--%.2lf\n", i , f[i], p[i]);
printf("%.2lf", f[n]);
return 0;
}
现在学会了正推,那么咱们来看看逆推,即从终点找到起点
我们令:==f(i)表示从i到n的期望距离==,那么我们想要的答案即为f(1)
如图:点j通过x1,x2,x3,… , xk到n, 点j到这K个点的距离为:w1, w2, w3 ,… , wk
这K个点到n点的期望距离分别为f1, f2, f3, … , fk
outj:表示j的出度,1/outj:即为j到这K个点的概率
那么我们会有:
$$
f(j) = \frac{f_1+w_1}{out_j} + \frac{f_2+w_2}{out_j} + \frac{f_3 + w_3}{out_j} + … + \frac{f_k + w_k}{out_j}\\ =\sum_{i = 1}^{k}{\frac{f_i+w_i}{out_j}}
$$
根据递推式我们可以看出我们想求f(j),那我们要求与j相连的点,而求这些相邻的点则要求这些点相邻的点,对你是不是发现,这是个递归回溯的过程,所以我们可以记忆化搜索来解。
关于式子中一个疑惑的解答
$$ 咱们先看j到x_k的这条路径的柿子:f(j) \overset{\text{+}}{=}\frac{f_k + w_k}{out_j}\\\ 这里\frac{w_k}{out_j}我理解不就是j到x_k的概率乘路径权值嘛,\\\但是\frac{f_k}{out_j}这个x_k 的期望也要乘j的概率呀??\\\ 来来来,看这里:咱们一开始就说了,从某个点到某个点的概率是会叠乘的,我们来看看式子中都表示什么含义:\\\f(x_k):仅表示从x_k到n的期望距离,不包含j这个点到x_k这个点概率的影响\\\f(j):从j到n的期望距离,而在路径上是会经过x_1,x_2,…,x_k这些点的 \\\所以我们在求f(j)的时候要将j到x_k点概率的影响加到f(x_k)上面即:f(j) \overset{\text{+}}{=}\frac{f_k + w_k}{out_j}\\\ 综上:我们使用逆推记忆化搜索的递推式应为:\\\f(j) = ((f(能到达状态的期望) + w(能到达状态的权值))\times P(j到能到达状态的概率) $$
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int n , m;
int dout[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++;
}
double dfs(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] += (dfs(j) + w[i])/ dout[u];
}
return f[u];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) h[i] = -1, f[i] = -1;
int a, b, c;
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
dout[a] ++;
}
f[n] = 0;
dfs(1);
printf("%.2lf", f[1]);
return 0;
}
p[j] += p[t] * 1.0 / out[t]; 正推那里,概率不是要叠乘吗?这里为什么用+=,求解答
叠乘是因为求一条路到一个点的过程中概率是要叠乘的求的是这条路径到这个点的概率;
而到这个点可能会有多条路径,每条路径的概率相加即为从起点到这个点的概率