Problem 4075 --永世乐土

4075: 永世乐土

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

某一日，从天坠落。人们抬头仰望，于是看见了星空。 星月送来神的女儿，她愿成为人的伴侣。 长风化作她的轺车，四海落成她的园圃。鸟雀衔来善的种子，百花编织爱的颂歌。 她便是这样降生于世，行于大地，与人类一同长大，与世界一起发芽。 而今，终焉之时将至。 而今，归去之时已至。 就此告别吧，美丽的世界。 此后，将有群星闪耀，因为我如今来过。 此后，将有百花绽放，因为我从未离去。 请将我的箭、我的花、与我的爱，织成新生的种子，带向那枯萎的大地。 然后，便让它开出永恒而无瑕的……人性之华吧。 【我名为爱莉希雅……】 【最初的律者，人之律者。】 为了寻求答案，雷电芽衣来到了往世乐土的至深之处，这里名为"永世乐土"，是爱莉希雅的记忆空 间，埋藏着"第十三律者"的秘密。爱莉希雅与芽衣约定，第二天早上一起去那座迷雾笼罩的小岛，去那 场"最后的宴会"发生的地点，一起见证"第十三律者"的诞生，和结束。 然而，第二天，爱莉希雅并没有出现…… Рис. 1: 来源：《因你而在的故事》 永世乐土是一张由 n 个点 m 条边构成的无向图。这里共有 k 位英桀记忆体，每位英桀记忆体存在于某 个点上，一个点上可以存在多位英桀记忆体。一开始，雷电芽衣位于 1 号点，接下来，芽衣可以沿着图 中的边，前往其他点。每当芽衣走过一条边之后，侵蚀之律者就会等概率随机选取一个未被侵蚀的点， 将之侵蚀（注意该过程发生在芽衣当次移动完成之后，下一次移动开始之前），侵蚀的效果为使得该点 上存在的所有英桀记忆体消失。芽衣知晓所有英桀记忆体的位置，并且可以立刻感知到哪个点被侵蚀 了。假设芽衣做出了最优选择，请计算她见到英桀记忆体数量的期望的最大值为多少。注意，如果芽衣 经过一条边后，侵蚀之律者选择侵蚀的点恰好与芽衣所到达的点相同，那么芽衣会先见到这个点上的英 桀记忆体，然后英桀记忆体马上消失。 

Input

第一行 3 个正整数 n, m, k(n ≤ 30, m ≤ 50, k ≤ 12)，分别表示点的数量、边的数量以及英桀记忆体的数 量。 接下来共 m 行，每行两个正整数 u, v(1 ≤ u, v ≤ n, u 6= v)，表示点 u 与点 v 之间有一条无向边。 接下来共 k 行，其中第 i 行一个正整数 xi(1 ≤ xi ≤ n)，表示第 i 为英桀记忆体所在的点的编号。

Output

仅一行一个整数，表示雷电芽衣能见到的英桀记忆体数量的期望的最大值。你的答案与参考答案的相对 误差或绝对误差不超过 10−6 时被认为是正确的。 

Sample Input复制

5 10 2
3 1
3 1
2 4
5 4
3 2
3 1
3 4
4 3
4 5
3 4
3
2

Sample Output复制

1.800000000

推荐代码 查看4075 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 2023年中国大学生程序设计竞赛女生专场 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛