洛谷P4316题解：拓扑排序+条件概率 | Yuhang's Blog

题目链接 这两天在看概率论，所以写一下这题更数学的理解方式。

如果设随机变量$X_i(1\le i\le m)$表示每条边在绿豆蛙行走路径中里贡献的长度（或者说绿豆蛙在这条边上行走了的长度），并设绿豆蛙经过边$i$为事件$Y_i$，则$X_i$服从分布： $$f(x)=\{\begin{array}{ll}1-Pr(Y_i),& x=0\\ Pr(Y_i),& x=w_i\end{array}$$ 其中$f(x)=Pr(X_i=x)$是概率分布函数。 由数学期望定义得到， $$E(X_i)=w_{i}Pr(Y_i)$$ 设行走路径总长度为随机变量$X$，则$X=\sum _{i=1}^n{X}_i$。由数学期望的性质得到： $$E(X)=E(\sum _{i=1}^n{X}_i)=\sum _{i=1}^{n}E(X_i)=\sum _{i=1}^n{w}_{i}Pr(Y_i)$$ 此时我们只需要去求$Pr(Y_i)$。设边$i$是从点$u$指向点$v$的。注意到绿豆蛙经过某条边的概率符合条件概率： $$Pr(Y_i)=Pr(\text{绿豆蛙经过}u)Pr(\text{绿豆蛙选择了边}i\mid \text{绿豆蛙经过}u)$$ 如果点$u$的出度是$k$，由题意知道 $$Pr(\text{绿豆蛙选择了边}i\mid \text{绿豆蛙经过}u)=\frac{1}{k}$$ 那么对于每个点$u$, 我们现在只需要去求$Pr(\text{绿豆蛙经过}u)$。这概率可以通过递推得到。综合上面的讨论，有： $$Pr(\text{绿豆蛙经过}u)=\sum _{s\to u\text{存在}}\frac{Pr(\text{绿豆蛙经过}s)}{s\text{的出度}}$$ 要做这个递推，拓扑排序即可。实际的运算就是在走到每个$s$的时候，把自己对经过$u$的概率的贡献（即$Pr(\text{绿豆蛙经过}s)/s\text{的出度}$）加过去。拓扑排序保证走到$u$时，$Pr(\text{绿豆蛙经过}u)$已经算好了。 因此最后的代码是这样：

#include<bits/stdc++.h>
#define N 112345
using namespace std;

inline int read(){
    int x=0; int sign=1; char c=getchar();
    while(c>'9'  c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}
vector<int> g[N];
vector<int> weight[N];
vector<int> topo;
int in_deg[N];
double point_pr[N];
int n, m;

void topo_sort(){
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (unsigned int i = 0; i < g[u].size(); i++){
            int v = g[u][i];
            in_deg[v]--;
            if (in_deg[v] == 0){
                q.push(v);
            }
        }
    }
}

double ans = 0.0; 
void calc(){
    point_pr[1] = 1.0;
    for(unsigned int i = 0; i < topo.size(); i++){
        int u = topo[i];
        int k = g[u].size();
        for (int j = 0; j < k; j++){
            int v = g[u][j];
            int w = weight[u][j];
            point_pr[v] += point_pr[u] / k;
            ans += (w * point_pr[u]) / k;
        }
    } 
}


int main(){
    //freopen("4316.in", "r", stdin);
    n = read(), m = read();
    for (int i = 1; i <= m; i++){
        int u = read(), v = read(), w = read();
        g[u].push_back(v);
        weight[u].push_back(w);
        in_deg[v]++;
    }

    topo_sort();

    calc();

    printf("%.2f\n", ans);

}

可以略作优化，实际上在拓扑排序过程中就能完成相关计算。但我懒的写了。 我很迷惑的是现在洛谷似乎不能提交题解了，至少这题不行。不知道什么原因。 为什么突然开始写算法题？快乐。（主要是在学数学）