P4316 绿豆蛙的归宿（期望）

P4316 绿豆蛙的归宿

因为非要用bfs所以稍微麻烦一点qwq（大家用的都是dfs）

其实问题让我们求的就是经过每条边的概率*边权之和

我们可以用bfs把图遍历一遍处理概率，顺便把每条边的概率*边权存到这条边的终点上

最后把每个点的答案累加起来，答案就出来了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cctype>

using namespace std;

inline int Int(){

    char c=getchar(); int x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

    return x;

}

const int maxn=;

int n,m,cnt,siz[maxn],hd[maxn],ed[maxn],nxt[maxn<<],to[maxn<<],in[maxn];

double ans,dis[maxn<<],f[maxn],p[maxn];

inline void add_edge(int x,int y,int v){

    nxt[ed[x]]=++cnt, ed[x]=cnt, hd[x]= hd[x] ?hd[x]:cnt;

    ++siz[x], ++in[y], to[cnt]=y, dis[cnt]=(double)v;

}

void bfs(int st){//bfs处理

    queue <int> h;

    h.push(st); p[st]=1.0; //初始概率为1

    while(!h.empty()){

        int x=h.front(); h.pop();

        double Q=p[x]/(double)siz[x]; //到从该点经过每条边的概率

        for(int i=hd[x];i;i=nxt[i]){

            p[to[i]]+=Q, f[to[i]]+=dis[i]*Q; --in[to[i]]; //p数组存储概率，f数组存储所求答案

            if(in[to[i]]<=) h.push(to[i]);

        }

    }

}

int main(){

    n=Int(); m=Int();

    int q1,q2,q3;

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

        q1=Int(); q2=Int(); q3=Int();

        add_edge(q1,q2,q3);

    }

    bfs();

    for(int i=;i<=n;++i) ans+=f[i]; //累加答案

    printf("%.2lf",ans);

    return ;

}