有向无环图

事件发生的期望的线性性$E(aX+bY) = aE(X)+bE(Y)$
$f[i]:从i跳到N的期望长度$
$边界:f[N]=0$
$答案:f[1]$

$$\begin{align} E(i)&=E(\frac{1}{k}(w_{1}+x_{1}) + \frac{1}{k}(w_{2}+x_{2}) +…+\frac{1}{k}(w_{k}+x_{k}) )\\\\ &=\frac{1}{k}(w_{1}+E(x_{1})) +\frac{1}{k}(w_{2}+E(x_{2}))…+\frac{1}{k}(w_{k}+E(x_{k}))\\\\ &=\frac{1}{k}(w_{1}+w_{2}+…+w_{k})+\frac{1}{k}(E(x_{1})+E(x_{2})+…+E(x_{k}))\\\\ f(i)&=\frac{1}{k}(w_{1}+w_{2}+…+w_{k})+\frac{1}{k}(f(s_{1})+f(s_{2})+…+f(s_{k}))\\\\ &=\sum_{i=1}^{k}\frac{1}{k}(w_{i}+f(s_{i})) \end{align}$$

问题转化为按拓扑序从后往前推一遍

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dout[N];
double f[N];

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx]=c,h[a]=idx++;
}

double dp(int u)
{
    if(f[u]>=0)return f[u];
    f[u]=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        f[u]+=(w[i]+dp(j))/dout[u];
    }
    return f[u];
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        dout[a]++;
    }
    memset(f,-1,sizeof f);
    printf("%.2lf\n",dp(1));
    return 0;
}