• • 题目描述
    • 题目背景
    • 题目描述
    • 输入格式
    • 输出格式
    • 输入输出样例
    • 说明/提示
      • 数据规模与约定
  • 期望dp+拓扑排序
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

题目背景

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

题目描述

给出张 nn 个点 mm 条边的有向无环图，起点为 11，终点为 nn，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 kk 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \frac{1}{k}k1 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入格式

输入的第一行是两个整数，分别代表图的点数 nn 和边数 mm。

第 22 到第 (m + 1)(m+1) 行，每行有三个整数 u, v, wu,v,w，代表存在一条从 uu 指向 vv 长度为 ww 的有向边。

输出格式

输出一行一个实数代表答案，四舍五入保留两位小数。

输入输出样例

输入 #1复制

4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4

输出 #1复制

7.00

说明/提示

数据规模与约定

• 对于 20%20% 的数据，保证 n \leq 10^2n≤102。
• 对于 40%40% 的数据，保证 n \leq 10^3n≤103。
• 对于 60%60% 的数据，保证 n \leq 10^4n≤104。
• 对于 100%100% 的数据，保证 1 \leq n \leq 10^51≤n≤105，1 \leq m \leq 2 \times n1≤m≤2×n，1 \leq u, v \leq n1≤u,v≤n，1 \leq w \leq 10^91≤w≤109，给出的图无重边和自环。

期望dp+拓扑排序

分析

用f[i]表示i点到n点的期望路径长度，f[n] = 0

那么如果途中存在\(k\)条从\(u\)指向\(v_i\)的边：

$f[u] = \frac{\sum_{i=1}^k (f[v_i] + w[u][v_i])}{degree[u]} $

使用反向建立边 + 拓扑排序，逆序求出每个f[i]，最终结果就是f[1]

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue> 
using namespace std;
const int N = 100010;
struct VER
{
	int to, w;
};
vector<VER> h[N];
void add (int a, int b, int w)
{
	VER ver;
	ver.to = b, ver.w = w;
	h[a].push_back(ver);
}

int n,m;
int deg[N]; // 入度
int fixdeg[N]; // 

double f[N]; // f[i]表示i点到n点的路径长度的期望 

void topo()
{
	queue<int> q;
	
	q.push(n); // 起点是n，终点是1 
		
	while(!q.empty())
	{
		int t = q.front();
		q.pop();
		
		for(int i = 0; i < h[t].size(); i++)
		{
			int j = h[t][i].to, w = h[t][i].w; // t -> j这条边，权重为w 
			
			f[j] += (double)(f[t] + w)/(double)fixdeg[j]; // 期望计算公式 
			
			deg[j]--;
			if(!deg[j]) q.push(j);
		}
	}
} 

int main()
{
	scanf("%d%d", &n, &m);
	while(m --)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		add(b, a, w); // 反向建边 b->a : w	
		deg[a]++; // a点入度+1 
		fixdeg[a]++;
	}	
	
	topo(); // 拓扑排序 
	
	printf("%.2lf\n", f[1]);
	return 0;
}

时间复杂度

参考文章

https://www.cnblogs.com/five20/p/9381890.html

https://www.luogu.com.cn/blog/new2zy/solution-p4316