本文主要是介绍蓝桥集训之绿豆蛙的归宿，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓝桥集训之绿豆蛙的归宿
-
核心思想：数学推导 + 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;}
这篇关于蓝桥集训之绿豆蛙的归宿的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
