概率期望小结

P4316 绿豆蛙的归宿

典型的期望 dp。思路就是反向建图加反向跑 dp。

式子是这样的：
\(\large dp[v]=\sum \frac{dp[u]+w[u \ to \ v]}{indeg[v]}\)

然后遍历图可以使用拓扑排序或者深搜。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct node{
	int to,next;
	double w;
}edge[200101];
int indeg[200100],dx[200001];
int head[201001],cnt;
double dp[200100];
void add(int u,int v,int w)
{
	edge[++cnt].next=head[u];
	edge[cnt].to=v;
	edge[cnt].w=w;
	head[u]=cnt;
}
void toposort()
{
	queue<int>q;
	q.push(n);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			dp[v]+=(dp[u]+edge[i].w)/dx[v];
			indeg[v]--;
			if(!indeg[v]) q.push(v);
		}
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(v,u,w);
		indeg[u]++,dx[u]++;
	}
	toposort();
	printf("%.2lf",dp[1]);
}