昆明做网站建设公司/创意设计

LINK

题意

一张有向无环图,你从$1$号点出发

每天会随机走相邻的点或停在当前格子,花费为当前已走天数

求到达$n$号点的期望花费。

---

要知道花费,就必须知道当前是第几天,这显然是不现实的。

不妨定义$f[i]$表示当前在点$i$,到达$n$还需要的期望天数

再定义$g[i]$表示当前再点$i$,到达$n$的期望花费

设$i$有$k-1$个点可以转移,那么有转移方程

$f[i]=\frac{1}{k}\ast \sum _{(i,v)}f[v]+\frac{1}{k}\ast f[i]+1$

化简得到$f[i]=\frac{1}{k-1}\sum _{(i,v)}f[v]+\frac{k}{k-1}$

那么递推$g$就方便了

$g[i]=\frac{1}{k}\ast \sum _{(i,v)}(g[v]+f[v])+\frac{1}{k}\ast (g[i]+f[i])+1$

化简得到$g[i]=\frac{1}{k-1}\ast \sum _{(i,v)}\ast (g[v]+f[v])+\frac{1}{k-1}\ast f[i]+\frac{k}{k-1}$

最后$g[1]$就是答案。

有点类似费用提前的思想吧。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
vector<int>vec[maxn];
int t,n,m,vis[maxn];
double f[maxn],g[maxn];
void dfs(int u)
{f[u] = g[u] = 0;if( u==n )	return; //终点 vis[u] = 1;	int k = 1;for(auto v:vec[u] ){if( vis[v]==0 )	dfs(v);	k++;f[u] += f[v];g[u] += g[v]+f[v];}f[u] = ( f[u]+k )/(k-1.0);g[u] = ( g[u]+f[u]+k )/(k-1.0);
}
int main()
{cin >> t;while( t-- ){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int l,r; scanf("%d%d",&l,&r);vec[l].push_back( r );}dfs(1);printf("%.2f\n",g[1] );for(int i=1;i<=n;i++)	vec[i].clear(),vis[i] = 0;}
}