题目简述
给定一个有向无环图，求起点到终点的路径长度期望（从某一点走向各子节点的概率均等）。
思路
对于一个点，如果它的出度为 $K$，那么走向每一点的概率就是 $\frac{1}{k}$。每一个点，$K$ 是不尽相同的，所以我们难以直接线性地计算路径的期望。我们可以采用树形 DP 的思路，以起点作为祖先，用路径中靠近终点的点不断往上更新。
用f[i]表示 i 号节点到终点的路径长度期望——终点没有出度，到自身的路径长度期望为 0，可以很容易得到f[n] = 0。顺应这这个思路，将f[n]作为初始状态，由起点作为 DFS 入口，搜到终点后更新状态。对于点 x 的每一条出边 i，连接子节点为 y 有 f[x] += (f[y] + edge[i].edgeValue) / outdu[x];
值得注意的两点：
- 对于点 x 的每一个字节点 y，都要先递归 DFS 再累加答案——答案是在递归中「归」的不分累加的，不往下搜就累加了个寂寞
- 对于点 x 的出度，其影响范围不仅在于这一层的边对于答案的贡献，还有之后所有边对于答案的贡献——先要走到一条指定的边才能走这条边的终点所连的边，所以要用累加的结果除以出度
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MaxN = 100005;
struct Edge{
int nextEdge, destinationVertex, edgeValue;
}edge[MaxN * 2];
int n, m, tot, head[MaxN], outdu[MaxN];
double f[MaxN];
bool vis[MaxN];
inline void AddEdge(int u,int v,int w){
tot++;
edge[tot].nextEdge = head[u];
edge[tot].destinationVertex = v;
edge[tot].edgeValue = w;
outdu[u]++;
head[u] = tot;
}
void DFS(int x){
if(x == n){f[x] = 0; return;}
if(vis[x]) return;
vis[x] = true;
for(int i = head[x]; i; i = edge[i].nextEdge){
int y = edge[i].destinationVertex;
DFS(y);
f[x] += (double)((f[y] + edge[i].edgeValue) / outdu[x]);
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
int u, v, w;
scanf("%d%d%d",&u,&v,&w);
AddEdge(u,v,w);
}
DFS(1);
printf("%.2lf\n",f[1]);
return 0;
}