蓝桥集训之绿豆蛙的归宿 核心思想：数学推导 + 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

Description 随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。 给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？ Input

题目大意: 若一个点有 k k k条出边，则走每条出边的概率均为1k1k\tfrac{1}{k}。给出一个有向无环图，求从起点走到终点的所经过的路径总长度期望。 Input I n p u t Input 4 41 2 11 3 22 3 33 4 4 Output O u t p u t Output 7.00 思路： 这很明显是一道数学期望的题目。但是由于之

点击这里查看原题 f[i]表示从i到N的期望，因此f[i]为i能到的各个点的期望+边权的和除k。 /*User:SmallLanguage:C++Problem No.:3036*/#include<bits/stdc++.h>#define ll long long#define inf 999999999using namespace std;const int M=1e

Description 随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。 给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？ Input 第一行: 两

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