[题解] [LuoguP4316] 绿豆蛙的归宿

一.前言

今天本着停课不停学的决心，看了看数学期望。结果是见不熟悉之数学起身慌而走之。话虽然这么说，但是例题还是要做的，题解也是要写的。凭本人小学水平数学，粗略的理解数学期望就是操作的足够多了之后趋于平均的一个？的东西。，嘛，就相当于骰子扔多了平均值就会趋于一个常数，但是怎么都不会扔出7就对了。（此处为古贺朋绘酱默哀qwq，永远都做不出自己想要的梦~~我永远喜欢古贺朋绘~~）

二.题意简述

说了一个大点的废话以后，进入这一篇的正题。

题意：在一个有向无环图中，给出各边的信息，求从起点走到终点的路径长度期望。（顺带一提选择每条边的概率是一样的）

三.思路

那么知道了题意之后，很明显的这是个DP。（别问我怎么看出来的问就无效性），那么我们设置从 i 点到终点的路径长度期望为 (f[i]) ，当前 i 的出度为 (out[i]) ,选中的边所对的点为 v ，边的长度为 (dis(i,v))，就可以得出递推式。

[f[i]=frac{sum (f[v]+dis(i,v))}{out[i]} ]

ε=(´ο｀*)))为什么是这样呢？首先为了平均要除以一个出度是没有问题的（毕竟从终点往前推，同时这里实现的时候可以用分配律搞搞），然后由于是路径长所以是加而不是乘。（不知道这样讲能不能看懂），然后边界条件是 (f[n]=0).（显然）

虽然说起来是DP，但是实际的应用是DFS，毕竟在图上又要遍历，之类的。

四.CODE

const int MAXN=200005;
int n,m;
int head[MAXN],ne[MAXN],to[MAXN],dis[MAXN],tot,out[MAXN];
inline void add(int x,int y,int z){
	to[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
	dis[tot]=z;
}
double f[MAXN];
bool vis[MAXN];
void dfs(int x){
	if(x==n){
		f[x]=0;
		return ;
	}
	if(vis[x])return;
	vis[x]=1;
	for(int i=head[x];i;i=ne[i]){
		int v=to[i];
		dfs(v);
		f[x]+=(f[v]+1.0*dis[i])/out[x];
	}
}
int main(){
n=read();m=read();
m_for(i,1,m){
	int x=read(),y=read(),z=read();
	add(x,y,z);
	out[x]++;
}
dfs(1);
printf("%.2f",f[1]);
return 0;
}

五.后记

其实由于某种奇奇怪怪的原因，好像可以先拓扑一下路径再操作，会快一些（大概）