P4819 [中山市选] 杀人游戏

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

无

无

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