题意：给一个有向无环图，起点是1，终点为n，选择每一条边的概率一样，求起点到终点的所经过的路径的期望长度。
思路：设f[x]表示从节点x走到终点所经过的路径的期望长度，若从x出发有k条边，分别到达y1,y2...yk,边长为z1,z2...zk，
所以根据数学期望的定义和性质，有：f[x]=1/k*∑(F[yi]+zi)
显然f[N]=0，我们的目标是求f[1],所以我们从终点出发，在反向图拓扑排序，求f[x]。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<vector> #include<string> #include<set> #define ll long long using namespace std; const int N=200000+100; int ver[N],edge[N],nextt[N],head[N]; int out[N],deg[N]; int n,m,tot; double dis[N]; queue<int> q; void add(int x,int y,int z) { ver[++tot]=y; edge[tot]=z; nextt[tot]=head[x]; head[x]=tot; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(y,x,z); deg[x]++; out[x]++; } q.push(n); while(q.size()) { int x=q.front(); q.pop(); for(int i=head[x];i;i=nextt[i]) { int y=ver[i]; dis[y]+=(dis[x]+edge[i])/deg[y]; out[y]--; if(out[y]==0) q.push(y); } } printf("%.2lf\n",dis[1]); }
原文：https://www.cnblogs.com/2462478392Lee/p/11332647.html