概率与期望
期望
概率这一个词语在生活中实际上是经常会碰见的，所以说这里我就来说一说相对而言遇到的要少一些的期望。这个期望啊，可以理解为某些事件大量发生以后的平均的结果。这就好比一个六面的色子扔了很多很多次以后，色子平均值会趋近于3.5。这个原因啊，是显而易见，毫无疑问的，就不需要再多解释了。
例题
好的，有一道例题可以看看
洛谷P4316
这一道题啊，读完了我就想到了拓扑排序，，同时用两个变长数组来存就可以了最开始我想用边集，可是我不知道怎么用边集来拓扑排序啊，于是ZhuFN大佬提醒我用两个变长数组。因此，我们只需要用两个变长数组，一个用来存点,一个用来存权值就OK了。
而这一个拓扑排序的过程中，相对与普通的拓扑排序，增加上对于期望长度的累加就可以了这是因为期望具有可加性
$probab(u)$来的那一个点的期望长度，w为这一条边的权值，$outdgr(v)$为有几条路进来，那么可以得到
$$
probab(v)=[probab(u)+w]/outdgr(v)
$$
我们这里可采用正着来或反着来（应该是吧），就像是$USACO$的数字金字塔一样吧
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
| #include<bits/stdc++.h>
#define maxn 100005
using namespace std;
queue<int> Q;
vector<int>G[maxn];
vector<int>W[maxn];
int n,tmp=0;
int indgr[maxn];
int outdgr[maxn];
double probab[maxn];
int m;
void topsort(){
Q.push(n);
while(!(Q.empty())){
int u=Q.front();
Q.pop();
vector<int>::iterator iterG=G[u].begin();
vector<int>::iterator iterW=W[u].begin();
while(iterG!=G[u].end()){
int v=*iterG,w=*iterW;
indgr[v]--;
probab[v]+=(probab[u]+w)/(outdgr[v]);
if(!indgr[v]){
Q.push(v);
}
iterW++;iterG++;
}
}
}
int main(){
memset(indgr,0,sizeof(indgr));
memset(outdgr,0,sizeof(outdgr));
memset(probab,0,sizeof(probab));
scanf("%d%d",&n,&m);
int a,b,c;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
indgr[a]++;outdgr[a]++;
G[b].push_back(a);
W[b].push_back(c);
}
topsort();
printf("%.2lf",probab[1]);
return 0;
}
|
这里再附上另外的大佬这道题的链接，我是看了dyx大佬代码以后才发现自己累加的地方做错了的对，没错，我最开始错了,而 ZhuFN则是用的dfs做的。
dyx
zfn
那么就可以了