P4316 绿豆蛙的归宿

题意翻译

「Poetize3」

题目背景

随着新版百度空间的上线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。

题目描述

给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入输出格式

输入格式：

第一行: 两个整数 N M，代表图中有N个点、M条边第二行到第 1+M 行: 每行3个整数 a b c，代表从a到b有一条长度为c的有向边

输出格式：

从起点到终点路径总长度的期望值，四舍五入保留两位小数。

输入输出样例

输入样例#1：

输出样例#1：

7.00

说明

对于20%的数据 N<=100

对于40%的数据 N<=1000

对于60%的数据 N<=10000

对于100%的数据 N<=100000，M<=2*N

根据题意，总的期望路径长度$=\sum$每条边经过的概率*每条边的权值

又因为是有向无环图，所以每条边经过的概率等于经过这条边的终点的概率

这样的话我们就可以在拓扑排序的过程中进行计算

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxn = 1e5+3;

using namespace std;

queue<int> Node;

double f[maxn], ans, dis[maxn];

int n, m, indgr[maxn], cnt = 1, oudgr[maxn];

int first[maxn*2], next[maxn*2], u[maxn*2], v[maxn*2], w[maxn*2];

inline int read() {

	int x = 0, f = 1;

	char c = getchar();

	while (c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while (c <= '9' && c >= '0') {

		x = x*10+c-'0';

		c = getchar();

	}

	return x * f;

}

int main() {

	n = read(), m = read();

	memset(first, -1, sizeof(first));

	for(int i=1; i<=m; i++) {

		u[i] = read(), v[i] = read(), w[i] = read();

		indgr[v[i]] ++;

		oudgr[u[i]] ++;

		next[i] = first[u[i]];

		first[u[i]] = i;

	}

	for(int i=1; i<=n; i++)

		if(!indgr[i]) {

			Node.push(i);

			f[i] = 1.0;

		}

	while (cnt < n) {

		int x = Node.front();

		Node.pop();

		int k = first[x];

		while (k != -1) {

			indgr[v[k]]--;

			double s = (double(f[u[k]])/double(oudgr[u[k]]));

			f[v[k]] += (double(f[u[k]])/double(oudgr[u[k]]));

			ans += s * w[k];

			if(indgr[v[k]] == 0) {

				Node.push(v[k]);

				cnt++;

			}

			k = next[k];

		}

	}

	printf("%.2lf", ans);

	return 0;

}

巴特西

Luogu P4316 绿豆蛙的归宿