《算法竞赛进阶指南》0x38概率与数学期望 绿豆蛙的归宿
题目链接：https://www.acwing.com/problem/content/219/
题目给出一张有向无环图，要求从1到n的路径长度的数学期望，如果一个点有k条出边，那么走每条表的概率都是1/k，我们容易知道，记一个点x到终点n的路径的数学期望是dis[x]，那么dis[x]计算的结果依赖于他所能到达的所有的边，根据这个性质可以发现是跟拓扑排序有关系的，满足这样一种结构：在这个点处理之前它的所有可达的点都已经处理完了。
所以这个问题需要在拓扑排序的同时进行更新操作，需要建立反图，建反图是为了从可达点到该点进行更新。信息的传递是从终点开始的，所以需要建立一张反图进行反向递推。
代码：
#include<iostream> #include<cstdio> #include<queue> using namespace std; const int maxn = 100010; int head[maxn],nxt[maxn*2],ver[maxn*2],len[maxn*2]; int n,m; int tot=0; int deg[maxn],out[maxn]; double dis[maxn];//记录点i到n的路径数学期望 void addedge(int u,int v,int w){ ver[++tot]=v; len[tot]=w; nxt[tot]=head[u]; head[u]=tot; } int main(){ cin>>n>>m; int u,v,w; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); addedge(v,u,w);//建反图 deg[u]++; out[u]++; } queue<int> q; q.push(n); while(q.size()){ int x=q.front(); q.pop(); for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; dis[y]+=(dis[x]+(double)len[i])/deg[y]; if(--out[y]==0)q.push(y); } } printf("%.2lf ",dis[1]); }