[数据结构与算法]Acwing 217. 绿豆蛙的归宿

Acwing 217. 绿豆蛙的归宿

题意：

给出一个有向无环的连通图，起点为 1，终点为 N，每条边都有一个长度。

数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。

到达每一个顶点时，如果有 K 条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K。

现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

题解：

这个文章讲的不错
设dp[x]表示状态为x到终点n的期望路径总长，显然dp[n] = 0,所以要从dp[n]倒着推dp[1]
我们设一条有向边，x->y,那么就有：
dp[x] = P * ∑dp[y] + w[x->y]
P = (1/degree(x))，degree(x)为x的出度，有多少出度说明有多少种选择，概率就是倒数
w表示转移对答案的贡献
dp可以通过记忆化搜索求，也就通过拓扑排序求

代码：

记忆化搜索

#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b);
typedef long long ll;
using namespace std;

inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=3e5+9;
vector<pair<int,int> >vec[maxn]; 
double dp[maxn];
int n,m;
double dfs(int u){
	if(u==n)return 0;
	if(dp[u])return dp[u];
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i].first;
		int w=vec[u][i].second;
		dp[u]+=dfs(v)+w;
	}
	dp[u]=dp[u]/int(vec[u].size());
	return dp[u];
}
int main()
{
	
	cin>>n>>m;
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		vec[u].push_back({v,w});
	}
	
	printf("%.2f",dfs(1));
}

拓扑排序

时间复杂度O(n+m)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()//读优
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;}
const int maxn=100003;
const int maxm=200003;
struct Edge
{
    int from,to,w;
}p[maxm];
int n,m,cnt,head[maxm],in[maxn],dg[maxn];
double f[maxn];//f[x]表示x点到终点n的期望路径总长 
inline void add_edge(int x,int y,int W)//加边
{
    cnt++;
    p[cnt].from=head[x];
    head[x]=cnt;
    p[cnt].to=y;
    p[cnt].w=W;
}
inline void toposort()//拓扑排序
{
    queue <int> q;
    q.push(n);
    while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=p[i].from)
                {
                    int y=p[i].to;
                    f[y]+=(f[x]+p[i].w)/dg[y];//dp转移 
                    if(!(--in[y]))q.push(y);
                }
        }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),w=read();
            add_edge(y,x,w);//反向建图 
            in[x]++,dg[x]++;
        }
    toposort();
    printf("%.2lf\n",f[1]);
    return 0;
}