洛谷P4316题解：拓扑排序+条件概率

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

如果设随机变量$X_i(1\le i \le m)$表示每条边在绿豆蛙行走路径中里贡献的长度（或者说绿豆蛙在这条边上行走了的长度），并设绿豆蛙经过边$i$为事件$Y_i$，则$X_i$服从分布： $$ f(x) = \begin{cases} 1-\Pr (Y_i), & x=0 \newline \Pr (Y_i), & x = w_i \end{cases} $$ 其中$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);

}

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