欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-08 17:30:43
算法竞赛进阶指南,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]。#...

算法竞赛进阶指南,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