题解 | #绿豆蛙的归宿#

全概率公式

由于是一个有向无环图，因此可以考虑以拓扑序求取答案;

通过每个点的前驱节点的信息推导出当前节点的值，记当前节点为 ，的前驱节点是, 如果只可能由到达，那么显然, 但问题是，假如 节点有k个前驱节点，每个前驱节点占有的权重应该是多少，此时我们考虑全概率公式，记从起点出发经过到达的概率是 , 则

全概率公式可以大致理解为: 将一个复杂事件的发生概率，分解为在各种不同前提条件下发生概率的加权总和

现在考虑从 到达 的 概率，若从起点到达 的概率为 那么又有个出边，那么从起点经过 到达 的概率 就是

因此代码如下

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
using pii=pair<int,int> ;
int main() {
    int n,m;cin>>n>>m;
    vector<vector<pii > >adj(n+1),to_me_rec(n+1);
    vector<int> deg(n+1),out_cnt(n+1);
    
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[u].emplace_back(v,w);
        to_me_rec[v].emplace_back(u,w);
        deg[v]++,out_cnt[u]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!deg[i])q.emplace(i);
    }
    vector<double> p(n+1), E(n+1);
    p[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        double p_sum=0;
        for(auto [x,w]:to_me_rec[u]){
            E[u]+=(E[x]+w)*p[x]/out_cnt[x];
            p_sum+=p[x]/out_cnt[x];
        }
        if(p_sum!=0)E[u]/=p_sum;

        for(auto [v,w]:adj[u]){
            p[v]+=p[u]/cnt[u];
            deg[v]--;
            if(!deg[v])q.emplace(v);
        }
    }
    cout<<fixed<<setprecision(2)<<E[n]<<endl;
}