luogu#P11046. [蓝桥杯 2024 省 Java B] 星际旅行

    ID: 14973 远端评测题 2000ms 512MiB 尝试: 2 已通过: 0 难度: 3 上传者: 标签>2024广度优先搜索,BFS概率论期望蓝桥杯省赛

[蓝桥杯 2024 省 Java B] 星际旅行

题目背景

备注:原题(Java)时间限制 3.0s,空间限制 512 MB。

题目描述

小明国庆节准备去某星系进行星际旅行,这个星系里一共有 nn 个星球,其中布置了 mm 道双向传送门,第 ii 道传送门可以连接 aia_ibib_i 两颗星球(aibia_i \neq b_i 且任意两颗星球之间最多只有一个传送门)。

他看中了一款 “旅游盲盒”,一共有 QQ 个盲盒,第 ii 个盲盒里的旅行方案规定了旅行的起始星球 xix_i 和最多可以使用传送门的次数 yiy_i。只要从起始星球出发,使用传送门不超过规定次数能到达的所有星球都可以去旅行。

小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买,他想知道能旅行到的不同星球的数量的期望是多少。

输入格式

输入共 m+Q+1m + Q + 1 行。

第一行为三个正整数 n,m,Qn, m, Q

后面 mm 行,每行两个正整数 aia_ibib_i

后面 QQ 行,每行两个整数 xix_iyiy_i

输出格式

输出共一行,一个浮点数(四舍五入保留两位小数)。

3 2 3
1 2
2 3
2 1
2 0
1 1
2.00

提示

【样例解释】

  • 第一个盲盒可以旅行到 1,2,31, 2, 3
  • 第二个盲盒可以旅行到 22
  • 第三个盲盒可以旅行到 1,21, 2

所以期望是 (3+1+2)/3=2.00(3 + 1 + 2) / 3 = 2.00

【数据范围】

  • 对于 20%20 \% 的评测用例,保证 n300n \leq 300
  • 对于 100%100 \% 的评测用例,保证 n1000n \leq 1000mmin{n(n1)2,5n}m \leq \min \left\{\dfrac{n(n - 1)}{2}, 5n\right\}Q50000Q \leq 500000yin0 \leq y_i \leq n1xin1 \leq x_i \leq n