洛谷 P4316 绿豆蛙的归宿（算法竞赛进阶指南，概率数学期望， 拓扑排序）

算法竞赛进阶指南，182 页，概率数学期望

本题要点：
1、dis[x] 表示点x到终点所有经过的路径的期望长度。如果从点x出发有k条边，
分别到达 y[1], y[2], …, y[k], 边长分别是 z[1], z[2], …, z[k]那么
dis[x] = 1 / k * sum{dis[y[1]] + z[1], dis[y[2]] + z[2], …, dis[y[k]] + z[k]}
显然 dis[n] = 0;
2、建立原来图的反向图，求反图的拓扑排序，顺便计算每一点的 dis[i]。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MaxN = 100010, MaxM = 200010;
int ver[MaxM], edge[MaxM], Next[MaxM], head[MaxN];
int in_deg[MaxN], deg[MaxN];
int n, m, tot;
double dis[MaxN];
queue<int> q;	//拓扑排序

void add(int x, int y, int z)
{
	ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

int main()
{
	int x, y, z;
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; ++i)
	{
		scanf("%d%d%d", &x, &y, &z);
		add(y, x, z);	//建立反图
		in_deg[x]++, deg[x]++;	//in_deg 用于拓扑排序， deg[x] 表示点x 的入度总数
	}
	q.push(n);
	while(q.size())
	{
		int y = q.front(); q.pop();	
		for(int i = head[y]; i; i = Next[i])
		{
			int x = ver[i];
			dis[x] += (dis[y] + edge[i]) / deg[x];
			in_deg[x]--;
			if(!in_deg[x])
			{
				q.push(x);
			}
		}
	}
	printf("%.2lf\n", dis[1]);
	return 0;
}

/*
4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4
*/

/*
7.00
*/

本文地址：https://blog.csdn.net/qq_38232157/article/details/107347518