#2438. [中山市选2011]杀人游戏

[中山市选2011]杀人游戏

题目描述

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

输入格式

第一行有两个整数 N,M。 接下来有 M 行,每行两个整数 x,y,表示 x 认识 y(y 不一定认识 x) 。

输出格式

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

5 4 
1 2 
1 3 
1 4 
1 5 

0.800000 

提示

警察只需要查证 1。假如1是杀手,警察就会被杀。假如 1不是杀手,他会告诉警 察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概 率是0.8。对于 100%的数据有 1≤N ≤  10 0000,0≤M ≤  30 0000 数据已加强!

题目来源

没有写明来源