[BZOJ 3036]绿豆蛙的归宿：期望DP

本文主要是介绍[BZOJ 3036]绿豆蛙的归宿：期望DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

f[i]表示从i到N的期望，因此f[i]为i能到的各个点的期望+边权的和除k。

/*
User:Small
Language:C++
Problem No.:3036
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=1e5+5;
double f[M];
int fir[M],n,m,tot,sum[M];
bool vis[M];
struct edge{int v,w,nex;
}e[M<<1];
void add(int u,int v,int w){e[++tot]=(edge){v,w,fir[u]};fir[u]=tot;sum[u]++;
}
void dfs(int u){if(vis[u]) return;vis[u]=1;for(int i=fir[u];i;i=e[i].nex){dfs(e[i].v);f[u]+=f[e[i].v]+e[i].w;}if(sum[u]) f[u]/=sum[u];
}
int main(){freopen("data.in","r",stdin);//scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);}dfs(1);printf("%.2lf\n",f[1]);return 0;
}

这篇关于[BZOJ 3036]绿豆蛙的归宿：期望DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---