P4316 绿豆蛙的归宿 题解

P4316 绿豆蛙的归宿 题解

绿豆蛙的归宿

题目背景

随着新版百度空间的上线，Blog 宠物绿豆蛙完成了它的使命，去寻找它新的归宿。

题目描述

给出张 n n n 个点 m m m 条边的有向无环图，起点为 1 1 1，终点为 n n n，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 k k k 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 1 k frac{1}{k} k1​ 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入格式

输入的第一行是两个整数，分别代表图的点数 n n n 和边数 m m m。

第 2 2 2 到第 ( m + 1 ) (m + 1) (m+1) 行，每行有三个整数 u , v , w u, v, w u,v,w，代表存在一条从 u u u 指向 v v v 长度为 w w w 的有向边。

输出格式

输出一行一个实数代表答案，四舍五入保留两位小数。

样例 #1

样例输入 #1

4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4

样例输出 #1

7.00

提示

数据规模与约定

• 对于 20 % 20% 20% 的数据，保证 n ≤ 1 0 2 n leq 10^2 n≤102。
• 对于 40 % 40% 40% 的数据，保证 n ≤ 1 0 3 n leq 10^3 n≤103。
• 对于 60 % 60% 60% 的数据，保证 n ≤ 1 0 4 n leq 10^4 n≤104。
• 对于 100 % 100% 100% 的数据，保证 1 ≤ n ≤ 1 0 5 1 leq n leq 10^5 1≤n≤105， 1 ≤ m ≤ 2 × n 1 leq m leq 2 times n 1≤m≤2×n， 1 ≤ u , v ≤ n 1 leq u, v leq n 1≤u,v≤n， 1 ≤ w ≤ 1 0 9 1 leq w leq 10^9 1≤w≤109，给出的图无重边和自环。

铺垫知识—概率 D P DP DP和期望

概率DP

一、概率

概率DP，用动态规划的思想利用事件发生的概率。通过Dp来得到各阶段的发生概率。

在概率论中，我们把一个随机实验的某种结果称作为“样本点”，把所有可能事件构成的集合称作为“样本空间”。

在一个给定的样本空间中，随机事件就是样本空间的子集。即由若干个样本点构成的集合。

随机变量就是把样本点映射为实数的函数。随机变量分为离散型与连续型。我们主要讨论离散型变量，也就是取值优先或可数的随机变量。

定义：
设样本空间为 W ,对于 w中的每一个随机事件 A,都存在实值函数 P ( A ) P(A) P(A)，满足

P ( A ) ≥ 0 P(A)ge 0 P(A)≥0
P ( w ) = 1 P(w)=1 P(w)=1
对于若干个两两互斥的事件 A 1 , A 2 , … A n A_1,A_2,dots A_n A1​,A2​,…An​ 存在 ∑ P ( A i ) = P ( A i 交集 ) sum P(A_i)= P(A_i 交集) ∑P(Ai​)=P(Ai​交集)

所有的概率都是 0 ~ 1 之间的实数。

二、期望

若随机变量X的取值有 x 1 , x 2 … x_1,x_2dots x1​,x2​… ，一个随机事件可表示为 X= X i X_i Xi​ ,对应的概率为 P ( X = X i ) p i P(X=X_i)p_i P(X=Xi​)pi​。则称 E ( X ) = ∑ p i x i E(X)=sum p_ix_i E(X)=∑pi​xi​。为随机变量X的数学期望，也是说数学期望是随机变量取值与概率的乘积之和。

E ( c ) = c E(c)=c E(c)=c

E ( c x ) = c E ( x ) E(cx)=cE(x) E(cx)=cE(x)

E ( x + y ) = E ( x ) + E ( y ) E(x+y)=E(x)+E(y) E(x+y)=E(x)+E(y)

E ( x y ) = E ( x ) E ( y ) E(xy)=E(x)E(y) E(xy)=E(x)E(y)

满足线性函数 E ( a x + b y ) = a E ( x ) + b E ( y ) E(ax+ by)=aE(x)+bE(y) E(ax+by)=aE(x)+bE(y)

模型：

对于任意状态A,已知：

1. 状态A所有的后继状态

2. 设从状态A 转移到后继状态 B的概率 为 P(A,B),且 ∑ B P ( A , B ) = 1 sum_BP(A,B)=1 ∑B​P(A,B)=1

3. 设从状态A转移到后继状态的B的花费为W(A,B)

求解：从起点状态S到终点状态T的期望花费

一般方法：
将状态视为图上的节点。

设E(A) 表示从状态A到终止状态T的期望花费。设E(T)=0

那么得到状态转移公式：
E ( A ) = ∑ B P ( A , B ) × ( E ( B ) + W ( A , B ) ) E(A)=sum_BP(A,B)times (E(B) +W(A,B)) E(A)=B∑​P(A,B)×(E(B)+W(A,B))

当转移状态关系不成环时，状态转移为线性的。可以按照拓扑排序递推求解

若成环，列出所有的状态转移方程，利用’‘高斯消元’'解决

思路

铺垫知识一定要看！不然会看不懂这篇题解的！

我们先设

• dp[i]为从 i i i出发到终点 n n n的期望值
• G[i]为 i i i所有的出边的集合
  则，可以推出 d p [ u ] = ∑ e ∈ G [ u ] d p [ e . v ] + e . w G [ u ] . s i z e dp[u]=sum_{ein G[u]}frac{dp[e.v]+e.w}{G[u].size} dp[u]=∑e∈G[u]​G[u].sizedp[e.v]+e.w​

既然这道题目给的是一个 D A G DAG DAG（ D i r e c t e d A c y c l i c G r a p h Directed Acyclic Graph Directed Acyclic Graph）
也就是有向无环图，
直接拓扑！

这个时候，我们直接反向建边，从 n n n到 1 1 1按照拓扑序递推即可

还有一种记忆化搜索的思路，这里我就不讲了，
有兴趣的，看这里

A C C o d e AC Code AC Code

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N=1e5+5;
struct node{int v,w;
};
vector<node> G[N];
int out[N],cnt[N];
double dp[N];
queue<int> q;
int n,m;int main(){int u,v,w;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);G[v].push_back(node{u,w});out[u]++;cnt[u]++;}q.push(n);while(!q.empty()){int u=q.front();q.pop();for(auto e:G[u]){int v=e.v,w=e.w;dp[v]+=(dp[u]+w)/cnt[v];out[v]--;if(out[v]==0) q.push(v);}}printf("%.2f",dp[1]);return 0;
}

T h a n k y o u v e r y m u c h f o r r e a d i n g m y b l o g ! ! ! Thank you very much for reading my blog!!! Thank you very much for reading my blog!!!