绿豆蛙的归宿【期望】【DFS】

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

题目大意:

若一个点有 $k$ 条出边，则走每条出边的概率均为 $\tfrac{1}{k}$ 。给出一个有向无环图，求从起点走到终点的所经过的路径总长度期望。
$Input$

$Output$

7.00

思路：

这很明显是一道数学期望的题目。但是由于之前没有做过这类的题目，所以做起来还是很吃力。
拿样例来说
这里写图片描述

点 $1$ 一开始肯定是有1.00的几率到达的，它有两条出边，分别到达点 $2$ 和点 $3$ ，那么，点 $2$ 和点 $3$ 就各有0.50的几率到达。
这里写图片描述
那么，点 $2$ 又有一条出边到达点 $3$ ，那么点 $3$ 到达的几率就在原来的基础上又加上了点 $2$ 的到达几率，所以点 $3$ 的到达几率为1.00。

然后点 $3$ 就只有一条出边，通向点 $4$ ，所以点 $4$ 到达几率就为 $1.00$ 。
这里写图片描述

每次当我们访问到一个点时，就讲答案 $sum$ 加上它到达的概率 $\times$ 边权，即

s u m + = s [ x ] n u m [ x ] \times e [i] . d i s

$sum+=\tfrac{s[x]}{num[x]}\times e[i].dis$
且这个点的期望也要加上

s[x]num[x] s [ x ] n u m [ x ] $\tfrac{s[x]}{num[x]}$
然后继续向下搜索，搜到点

n n $n$ 时就返回，然后将期望值减去 $\tfrac{s[x]}{num[x]}$ ，防止重复计算。

代码：

#include <cstdio> #include <iostream> using namespace std;int n,m,x,y,t; double z,sum,s[300011],num[300011],head[300011],k;struct edge //邻接表 {int to,next;double dis; }e[500011];void add(int from,int to,double d) //建边 {t++;e[t].dis=d;e[t].to=to;e[t].next=head[from];head[from]=t; }void dfs(int x) {if (x==n) return; //到达终点for (int i=head[x];i;i=e[i].next){int v=e[i].to;double l=s[x]/num[x]; //计算路径长度期望s[v]+=l; //加上期望sum+=e[i].dis*l; //答案dfs(v);s[v]-=l; //减掉期望} }int main() {scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%lf",&x,&y,&z);add(x,y,z); //建边num[x]++;}s[1]=1.00; dfs(1);printf("%0.2lf\n",sum);return 0; }

这篇关于绿豆蛙的归宿【期望】【DFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！