#P4168. [2015年湖南省队省队集训]幻想乡的地图
[2015年湖南省队省队集训]幻想乡的地图
[2015 湖南省队集训] 幻想乡的地图
题目描述
辉夜曾是住在月宫的公主。她找出一张幻想乡的地图,与永琳玩捉迷藏。地图是一张有 个点、 条边的无向连通图。游戏开始时,辉夜从所有点中等概率选出一个点 ,藏在那里。
每轮游戏,永琳从当前地图上仍存在的点中等概率选一个点 。若 ,游戏结束;否则辉夜会告诉永琳所有满足下述条件的点 :当前图中,从 到 的每一条路径都包含 。永琳从地图上删去 和这些已经排除的点,以及与它们相连的边,再开始下一轮。删除后的点不能再被选择或经过。
求永琳找到辉夜所需轮数的期望,找到辉夜的那一轮也计入。
输入格式
第一行一个正整数 。接下来 行,每行两个整数 (),表示地图上的一条无向边。
输出格式
输出一行一个实数,表示答案。允许绝对误差不超过 。
样例 #1
样例输入 #1
3
1 2
2 3
1 3
样例输出 #1
2.000000
样例说明
在该图中,任意一个未猜中的点都不会额外排除其他点。游戏在第 、、 轮结束的概率均为 ,因此期望为 。
数据规模与约定
全部数据满足 ,环的长度不超过 。对于任意点 和任意固定长度,最短路经过 且长度为该固定值的点对数不超过 。
原题共有 个测试点:第 至 点满足 ;第 点满足 ,且最长简单路径长度不超过环的长度;第 至 点满足 ,数据随机生成。原题前 点时限为 秒,其余为 秒。