BZOJ2438 [中山市选2011]杀人游戏 期望概率+tarjan

发布于 2017-07-27  3.31k 次阅读


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

Description

一位冷血的杀手潜入 Na-wiat,并假装成平民。警察希望能在 N 个人里面,
查出谁是杀手。
警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他
认识的人, 谁是杀手, 谁是平民。 假如查证的对象是杀手, 杀手将会把警察干掉。
现在警察掌握了每一个人认识谁。
每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。
问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多
少?

Input

第一行有两个整数 N,M。
接下来有 M 行,每行两个整数 x,y,表示 x 认识 y(y 不一定认识 x,例如胡锦涛同志) 。

Output

仅包含一行一个实数,保留小数点后面 6 位,表示最大概率。

Sample Input

5 4
1 2
1 3
1 4
1 5

Sample Output

0.800000

HINT

警察只需要查证 1。假如1是杀手,警察就会被杀。假如 1不是杀手,他会告诉警

察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概

率是0.8。对于 100%的数据有 1≤N ≤  10 0000,0≤M ≤  30 0000

数据已加强!

[/toggle]

考试的时候想的是警察一步一步确认凶手,还要缩减比例,所以完全想错了。警察是在同时完成所有调查工作,而且在同一个强连通分量中,警察只要调查一个人,剩下的人就都会被确认,即关系具有传递性。调查每个人,警察都有死亡的概率,所以最终存活的概率即为1-调查的人数/总人数。tarjan缩点建图,入度为0的点数即为需要调查的人数。注意,当目前图中仅剩一个孤立的点时,就不用调查那个点了,因为其他点均已确认,所以直接在建出的新图上跑个DFS最保险。

[toggle hide="no" title="代码" color=""]

 

[/toggle]


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