题解 P4316 【绿豆蛙的归宿】

· · 题解

有向图概率期望

考试的时候想了好久，其实就是去找到所有可以到达终点的路除以中间路过点的概率即可，每个点的概率即为其的出度

因为数据较小，所以我们可以用dfs，然后加点优化什么的就水到第一了（好吧，很快就不是了）

#include<queue>
#include<cstdio>
#define IL inline
#define LL long long
#define re register//一些优化。。。
#define r(i,a,b) for(re int i=a;i<=b;i++)
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)
using namespace std;char BB[1<<15],*S=BB,*T=BB;//输入优化配套
int n,m,x,y,z,l[100001],tot,k[100001];//l是邻接表数组，k是每个点的出度
double ans,g[100001];//g为每个点的概率，ans为最终答案
struct node{int next,to,w;}e[200001];
IL void add(re int x,re int y,re int z){e[++tot]=(node){l[x],y,z};l[x]=tot;return;}//建边
IL LL read()//输入优化
{
    LL f=0;re char c; 
    while(c=getchar(),c<=47||c>=58);f=(f<<3)+(f<<1)+c-48;
    while(c=getchar(),c>=48&&c<=57) f=(f<<3)+(f<<1)+c-48;
    return f;
}
IL void dfs(re int x,re int sum,re double gl)
{
    if(x==n) {ans+=sum*gl;return;}//到达终点统计答案，即为长度与概率之积，并求和
    for(int i=l[x];i;i=e[i].next) dfs(e[i].to,sum+e[i].w,gl*g[x]);//继续搜索
}
signed main()
{
    n=read();m=read();
    r(i,1,m){x=read();y=read();z=read();add(x,y,z);k[x]++;}//统计每个点的出度
    r(i,1,n) if(k[i])g[i]=1.0/k[i]; else g[i]=1;//计算概率，每个点的概率即为其出度，若其没有出度默认为1
    dfs(1,0,1.0);//搜索
    printf("%0.2lf",ans);//输出
}

后记

空间复杂度大概O(M)吧，时间复杂度:O(能过)，我觉得差不多吧。。。如果有知道复杂度的dalao可以在右边讨论区留言。