拓扑+期望

思路

因为每条边等概率,那么就很轻松了,我们先跑个拓扑,确定拓扑序之后,从最后一个点向前更新,初始是$f[n]=0$,能到n的点会获得$\frac{(w[i]+f[n])}{deg[u}$的期望长度,因为u的度数是$deg[u]$所以有$\frac{1}{deg[u]}$的概率走到$i$这条边上,一个点的期望被算好后就不会再变,所以他能到n,就会获得$f[n]$的期望长度,然后这样逆序处理好所有点的期望,最后结果就是$f[1]$

代码

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
//By AcerMo
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=200500;
int n,m;
double f[M];
int in[M],dg[M],ti[M];
int to[M],w[M],nxt[M],head[M],cnt;
inline void read(int &x)
{
x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return ;
}
inline void add(int x,int y,int z)
{
to[++cnt]=y;w[cnt]=z;nxt[cnt]=head[x];
head[x]=cnt;in[y]++;dg[x]++;
return ;
}
inline void topsort()
{
queue<int>q;int tot=0;
for (int i=1;i<=n;i++)
if (!in[i]) q.push(i);
while (q.size())
{
int u=q.front();q.pop();ti[++tot]=u;
for (int i=head[u];i;i=nxt[i])
if (--in[to[i]]==0) q.push(to[i]);
}
return ;
}
signed main()
{
read(n);read(m);int x,y,z;
for (int i=1;i<=m;i++)
read(x),read(y),read(z),add(x,y,z);
topsort();
for (int i=n;i>=1;i--)
{
x=ti[i];
for (int k=head[x];k;k=nxt[k])
f[x]+=(f[to[k]]+w[k]*1.0)/(dg[x]*1.0);
}
printf("%.2lf",f[1]);
return 0;
}