BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元

发布于 2017-09-26  4.33k 次阅读


[toggle hide="yes" title="题目" color=""]

题目描述

Morenan被困在了一个迷宫里。迷宫可以视为N个点M条边的有向图,其中Morenan处于起点S,迷宫的终点设为T。可惜的是,Morenan非常的脑小,他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点。这样,Morenan走的步数可能很长,也可能是无限,更可能到不了终点。若到不了终点,则步数视为无穷大。但你必须想方设法求出Morenan所走步数的期望值。

输入格式

第1行4个整数,N,M,S,T
第[2, M+1]行每行两个整数o1, o2,表示有一条从o1到o2的边。

输出格式

一个浮点数,保留小数点3位,为步数的期望值。若期望值为无穷大,则输出"INF"。

【样例输入1】

6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6

【样例输出1】

3.000

【样例输入2】

9 12 1 9
1 2
2 3
3 1
3 4
3 7
4 5
5 6
6 4
6 7
7 8
8 9
9 7

【样例输出2】

9.500

【样例输入3】

2 0 1 2

【样例输出3】

INF

【数据范围】

测试点
N
M
Hint
[1, 6]
<=10
<=100
[7, 12]
<=200
<=10000
[13, 20]
<=10000
<=1000000
保证强连通分量的大小不超过100
另外,均匀分布着40%的数据,图中没有环,也没有自环

[/toggle]

 

题目链接

和BZOJ3270比较相似,都是在图上高斯消元来转移状态。

观察数据范围,可以很明显地看出来必须先Tarjan缩点,之后在强连通分量里面进行高斯消元。

一开始仿照3270写了个正着推出的式子,发现不太好搞,于是重新倒着想了一遍。

设f[i]:从i点出发走到终点的期望步数,则f[T]=0,最后的答案就是f[S]。

对于有出边的点i,以及出边连接的终点j,我们可以由如下式子列出方程:

$$f[i]=\sum f[j]*p[i] +1 $$

其中p[i]为从i走到j的概率,其实就是i的出度的倒数。按照拓扑逆序进行计算,也就是从起点所在强连通分量出发,递归处理路径上所有的强连通分量,最后再处理当前位置的解。这样,如果j和i在同一强连通分量,直接编号,列出方程,如果不在,那么一定也已经算出了f[j],直接带入,算进常数项即可。

比较坑的是INF的判断,跑正反两遍DFS:

1.如果起点终点所在强连通分量不连通,则无法到达。

2.如果存在起点能到的点,到不了终点,则也是期望INF步。因为从起点到达该点存在一定概率,而从该点到达终点的期望步数是INF,所以从起点到终点的期望步数也是INF。当然,如果存在环,则步数不一定为INF,因为虽然有可能沿着环一直跑,但是这样的概率无限小,所以直接列方程干掉环即可。

(Tarjan重新建图之后代码好混乱,以后直接把与新图有关的变量放进namespace里吧)

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974