P4316 绿豆蛙的归宿 期望DP

时间：2022-01-26 02:58:49

P4316 绿豆蛙的归宿 期望DP

DAG上，每条边有边权，走向相连每条路的概率相等，问从起点到终点所经过的路径总长度期望

因为发现终点走到终点期望为0，定义\(f[i]\)从终点走到\(i\)所经过的路径总长度期望，所以\(f[n]=0\)。于是建反图，拓扑转移

\[f[v]+=\frac{w+f[u]}{edg[v]}
\]

\(edg[v]\)表示从节点\(v\)有\(edg[v]\)条路可走

#include <cstdio>

#include <queue>

#define MAXN 100010

using namespace std;

int head[MAXN],nxt[MAXN*2],vv[MAXN*2],ww[MAXN*2],tot;

inline void add_edge(const int &u, const int &v, const int &w){

	vv[++tot]=v;

	ww[tot]=w;

	nxt[tot]=head[u];

	head[u]=tot;

}

int read(){

    char ch;int s=0;

    ch = getchar();

    while(ch<'0'||ch>'9') ch=getchar();

    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();

    return s;

}

int rdu[MAXN],edg[MAXN],n,m;

double f[MAXN];

queue <int> q;

int main(){

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

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

		int u,v,w;

		u=read(),v=read(),w=read();

		add_edge(v, u, w);

		++edg[u];++rdu[u];

	}

	q.push(n);

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=nxt[i]){

			int v=vv[i],w=ww[i];

			f[v]+=(w+f[u])/edg[v];

			--rdu[v];

			if(rdu[v]==0) q.push(v);

		}

	}

	printf("%.2f\n", f[1]);

	return 0;

}

相关文章