因为非要用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=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } const int maxn=100002; int n,m,cnt,siz[maxn],hd[maxn],ed[maxn],nxt[maxn<<1],to[maxn<<1],in[maxn]; double ans,dis[maxn<<1],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]]<=0) h.push(to[i]); } } } int main(){ n=Int(); m=Int(); int q1,q2,q3; for(int i=1;i<=m;++i){ q1=Int(); q2=Int(); q3=Int(); add_edge(q1,q2,q3); } bfs(1); for(int i=1;i<=n;++i) ans+=f[i]; //累加答案 printf("%.2lf",ans); return 0; }