数学期望dp

期望dp

绿豆蛙的归宿

对于每个点，它的期望值 = 当前路径长度 / 起点的出度

所以我们先求出每个点的出度——无非就是在加入每条边的时候统计一下

根据数学期望的定义和性质，
\[F[x]=\frac{1}{k} \sum_{i = 1}^{k} (F[y_i ]+ z_i)\]
显然我们需要用逆推法，也就需要建反图，从\(F[N] = 0\)开始，求F[1]

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 200005;
int ver[N], edge[N], head[N], Next[N], tot;
int n, m, out[N], deg[N];
double f[N];
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z;
    Next[tot] = head[x], head[x] = tot;
}
int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
queue<int> q;
void bfs(){
    q.push(n);
    while(q.size()){
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i], z = edge[i];
            f[y] += (f[x] + z) / deg[y];
            out[y]--;
            if(out[y] == 0) q.push(y);
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x = read(), y = read(), z = read();
        add(y, x, z);
        deg[x]++, out[x]++;
    }
    bfs();
    printf("%.2f", f[1]);

    return 0;
}