Yuhang's Blog

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

2020-03-24 CodingMathematics

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

如果设随机变量Xi(1im)表示每条边在绿豆蛙行走路径中里贡献的长度(或者说绿豆蛙在这条边上行走了的长度),并设绿豆蛙经过边i为事件Yi,则Xi服从分布: f(x)={1Pr(Yi),x=0Pr(Yi),x=wi 其中f(x)=Pr(Xi=x)是概率分布函数。 由数学期望定义得到, E(Xi)=wiPr(Yi) 设行走路径总长度为随机变量X,则X=i=1nXi。由数学期望的性质得到: E(X)=E(i=1nXi)=i=1nE(Xi)=i=1nwiPr(Yi) 此时我们只需要去求Pr(Yi)。设边i是从点u指向点v的。注意到绿豆蛙经过某条边的概率符合条件概率: Pr(Yi)=Pr(绿豆蛙经过u)Pr(绿豆蛙选择了边i绿豆蛙经过u) 如果点u的出度是k,由题意知道 Pr(绿豆蛙选择了边i绿豆蛙经过u)=1k 那么对于每个点u, 我们现在只需要去求Pr(绿豆蛙经过u)。这概率可以通过递推得到。综合上面的讨论,有: Pr(绿豆蛙经过u)=su存在Pr(绿豆蛙经过s)s的出度 要做这个递推,拓扑排序即可。实际的运算就是在走到每个s的时候,把自己对经过u的概率的贡献(即Pr(绿豆蛙经过s)/s的出度)加过去。拓扑排序保证走到u时,Pr(绿豆蛙经过u)已经算好了。 因此最后的代码是这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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);

}

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