蓝桥集训之绿豆蛙的归宿

蓝桥集训之绿豆蛙的归宿

• 核心思想：数学推导 + dp

  • 

  • 用f[i] 存i到N的数学期望

  • 因此f[i] = [(w1+w2+…+wk) + f(s1) + f(s2) + … + f(sk)] / k == E(i)

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 100010 , M = 200010;
    
    int w[M],e[M],ne[M],h[N],idx;
    int n,m;
    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];  //公式 求u点期望
        }
        return f[u];
    }
    int main()
    {
        cin>>n>>m;
        memset(h, -1, sizeof h);
        while(m--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            dout[a] ++;  //记录a点有多少路出去
        }
        memset(f, -1, sizeof f);  //初始化期望数组 更新一次即可
        printf("%.2lf\n",dp(1));
        return 0;
    }