CH 3802/LUOGU 4316 绿豆蛙的归宿（概率与数学期望）

淩亂°似流年 2021-11-16 15:26 223阅读 0赞

## 题意：给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？ ##

## 分析：求期望，逆推法（建反图），详见《算法竞赛进阶指南》P182。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    int ver[200002], edge[200002], next[200002], head[100002];
    int out[100002], deg[100002];
    int n, m, tot;
    double dis[100002];
    queue<int> q;
    
    void add(int x, int y, int z) {
    	ver[++tot] = y, edge[tot] = z, next[tot] = head[x], head[x] = tot;
    }
    
    int main() {
    	cin >> n >> m;
    	for (int i = 1; i <= m; i++) {
    		int x, y, z;
    		scanf("%d%d%d", &x, &y, &z);
    		add(y, x, z); // 建反图
    		deg[x]++; out[x]++;
    	}
    	q.push(n);
    	while (q.size()) {
    		int x = q.front(); q.pop();
    		for (int i = head[x]; i; i = next[i]) {
    			int y = ver[i];
    			dis[y] += (dis[x] + edge[i]) / deg[y];
    			out[y]--;
    			if (out[y] == 0) q.push(y);
    		}
    	}
    	printf("%.2f\n", dis[1]);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，223人围观）

还没有评论，来说两句吧...

相关阅读

相关 21. 概率与统计 - 数学期望、统计描述&分布

文章目录数学期望方差标准差协方差二项分布高斯分布中心极限定理

我就是我/ 2024年03月02日 03:29/ 0 赞/ 76 阅读

相关 codevs2488 绿豆蛙的归宿 dfs

题目描述 Description 　　随着新版百度空间的上线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。　　给出一个有向无环图，起点为1终点为N，每条边都有一个

「爱情、让人受尽委屈。」/ 2024年02月17日 20:51/ 0 赞/ 62 阅读

相关 cf期望概率专题

cf1009E：求到第i段期望和的比较困难，但是单独求每段的期望是比较容易的，所以单独对每段求和，然后累计总和 E\[i\]=1/2\a1+1/4\a2+...+1/2^(i

傷城~/ 2023年10月12日 08:22/ 0 赞/ 75 阅读

相关概率期望dp

简易的入门：http://kicd.blog.163.com/blog/static/126961911200910168335852/ 大神的总结：http://blog

港控/mmm°/ 2023年08月17日 16:25/ 0 赞/ 158 阅读

相关 ZOJ 3822 Domination （概率期望）

ZOJ 3822 Domination（概率期望）：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=115193\

港控/mmm°/ 2022年08月21日 14:44/ 0 赞/ 68 阅读

相关【概率&数学期望】A Dangerous Maze LightOJ - 1027

Think: 1知识点：概率＆数学期望 2题意：（１）：T组测试数据（２）：每组测试数据，n扇门，每扇门对应一个xi，等概率进入任意一扇门，若进入门的xi为

梦里梦外;/ 2022年06月06日 01:52/ 0 赞/ 253 阅读

相关概率与期望学习心得

修正信息备注： 1.【2018-01-30】创作博文基础 2.【2018-01-30】增加样例2.2 一、基本定义 1.数学期望：在概率论和统计学中，数学期望(m

Love The Way You Lie/ 2022年06月01日 12:53/ 0 赞/ 247 阅读

相关数学题(期望+概率+快速幂)CodeForces 1009E-Intercity Travelling

数学题(期望+概率)CodeForces 1009E-Intercity Travelling -------------------- 题目链接：[E.

本是古典何须时尚/ 2022年05月17日 11:57/ 0 赞/ 224 阅读

相关【BZOJ3143】【Luogu P3232】 [HNOI2013]游走概率期望，图论

期望\\(DP\\)入门题目。关键思想：无向边的转移作为有向边考虑。其他的就是直接上全期望公式。由于这个题目不是有向无环图，所以需要高斯消元搞一搞。设每个点的期望经过次

Love The Way You Lie/ 2022年01月09日 10:51/ 0 赞/ 278 阅读

相关 CH 3802/LUOGU 4316 绿豆蛙的归宿（概率与数学期望）

题意：给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该

淩亂°似流年/ 2021年11月16日 15:26/ 0 赞/ 224 阅读