当前位置 博文首页 > ttoobne：2019南京网络赛 D. Robots（概率DP与拓扑排序）
题目链接
在做这道题之前看一个简化版：绿豆蛙的归宿
设
F
[
x
]
F[x]
F[x] 表示从
x
x
x 走到终点所经过的路径的期望长度。若从
x
x
x 出发有
k
k
k 条边，分别到达
y
1
,
y
2
.
.
.
y
k
y_1,y_2...y_k
y1?,y2?...yk? ，边长分别为
z
1
,
z
2
.
.
.
z
k
z_1,z_2...z_k
z1?,z2?...zk? ，则根据数学期望的定义和性质，有：
F
[
x
]
=
1
k
?
∑
i
=
1
k
(
F
[
y
i
]
+
z
i
)
F[x]=\frac{1}{k}*\sum_{i=1}^k(F[y_i]+z_i)
F[x]=k1??i=1∑k?(F[yi?]+zi?)
就可以将边取反然后用拓扑排序解决。
现在这道题在上面这道题的基础上相当于将边长设置为 1 ，然后多了一个每次多走一条边的花费。
每个点到
n
n
n 点的距离相当于：
F
d
a
y
[
i
]
=
1
d
e
g
[
i
]
+
1
?
∑
j
=
1
d
e
g
[
i
]
(
F
d
a
y
[
i
]
+
1
)
+
1
d
e
g
[
i
]
+
1
?
(
F
d
a
y
[
i
]
+
1
)
F_{day}[i]=\frac{1}{deg[i]+1}*\sum_{j=1}^{deg[i]}(F_{day}[i]+1)+\frac{1}{deg[i]+1}*(F_{day}[i]+1)
Fday?[i]=deg[i]+11??j=1∑deg[i]?(Fday?[i]+1)+deg[i]+11??(Fday?[i]+1)化简之后：
F
d
a
y
[
i
]
=
1
d
e
g
[
i
]
?
∑
j
=
1
d
e
g
[
i
]
F
d
a
y
[
i
]
+
1
d
e
g
[
i
]
+
1
F_{day}[i]=\frac{1}{deg[i]}*\sum_{j=1}^{deg[i]}F_{day}[i]+\frac{1}{deg[i]}+1
Fday?[i]=deg[i]1??j=1∑deg[i]?Fday?[i]+
