#PQJ1930x10151. QOJ 1930_10151
QOJ 1930_10151
2025 联合省选 第二试岁月(years) 岁月(years) 【题目背景】 希望大家一直记得我。 “希望大家永远忘了我。” 【题目描述】 小Y 有一个n 个节点、m 条边的带权.无.向.图G,节点由1 至n 编号。第i (1 ≤i ≤m) 条边连接ui 和vi,边权为wi。保证G 连通且没有重边自环。 小Y 预见到岁月将会磨灭图G 的痕迹,而这会导致一些边变成有向边,另一些边 直接消失。具体地,图G 历经岁月将会磨损为n 个节点的带权.有.向.图G′,其中对于第 i (1 ≤i ≤m) 条边,G′ 上 • 有1 4 的概率同时存在ui 向vi 和vi 向ui 的有向边,它们的边权均为wi; • 有1 4 的概率存在vi 向ui、边权为wi 的有向边,而不存在其反向边; • 有1 4 的概率存在ui 向vi、边权为wi 的有向边,而不存在其反向边; • 有1 4 的概率ui 和vi 之间没有边。 所有m 个随机事件是独立的。 小Y 认为一个无向图的核心是最小生成树,而一个有向图的核心是最小外向生成 树。称图G′ 的一个边子集E 是.外.向.生.成.树,当且仅当|E| = n −1 且存在一个节点x 可以只经过E 中的有向边到达图G′ 上的所有节点。图G′ 的.最.小.外.向.生.成.树即为图G′ 上边权和最小的外向生成树。 小Y 希望图的核心历经岁月侵蚀也保持不变,于是他想知道,有多大的概率,图 G′ 的最小外向生成树存在,且其边权和等于图G 的最小生成树边权和。 你需要将答案对(109 + 7) 取模。可以证明答案一定为有理数a b,其中a 和b 互质, 且b 不是(109 + 7) 的倍数。因此你输出的数x 需要满足0 ≤x < 109 + 7 且a ≡bx (mod 109 + 7),可以证明这样的x 唯一存在。 【输入格式】 从文件years.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行两个整数c, T,分别表示测试点编号和测试数 据组数,接下来输入每组测试数据。样例满足c = 0。 对于每组测试数据,第一行两个整数n, m,分别表示图G 的点数和边数,接下来 m 行,第i (1 ≤i ≤m) 行三个整数ui, vi, wi,描述图G 上的一条边。 【输出格式】 输出到文件years.out 中。 第5 页 共11 页
2025 联合省选 第二试岁月(years) 对于每组测试数据,输出一行一个整数,表示图G′ 的最小外向生成树存在且其边 权和等于图G 的最小生成树边权和的概率,对(109 + 7) 取模。 【样例1 输入】 1 0 2 2 2 1 3 1 2 1 4 3 3 5 1 2 2 6 1 3 2 7 2 3 2 【样例1 输出】 1 750000006 2 171875002 【样例1 解释】 该组样例共有2 组测试数据。 • 对于第一组测试数据,由于图上只有一条边,因此只要G′ 上有边,G′ 的最小外 向生成树边权和就一定等于G 的最小生成树边权和。G′ 上存在边的概率为3 4,故 答案为3 4,取模后的结果为750000006。 • 对于第二组测试数据,在所有22m = 64 种G′ 中,有13 种情况不满足G′ 的最小 外向生成树边权和等于G 的最小生成树边权和: – G′ 为空图; – G′ 仅包含一条有向边,共6 种情况; – G′ 仅包含两条有向边,且指向同一个节点,共3 种情况; – G′ 仅包含两条有向边,且构成一个二元环,共3 种情况。 由于所有情况等概率出现,因此答案为1 −13 64 = 51 64,取模后的结果为171875002。 【样例2】 见选手目录下的years/years2.in 与years/years2.ans。 该组样例共有5 组测试数据。其中每组测试数据分别满足测试点1 ∼3、4 ∼6、7, 8、 9 ∼11、12, 13 的限制。 第6 页 共11 页
2025 联合省选 第二试岁月(years) 【样例3】 见选手目录下的years/years3.in 与years/years3.ans。 该组样例共有5 组测试数据。其中每组测试数据分别满足测试点14 ∼16、17, 18、 19, 20、21 ∼23、24, 25 的限制。 【子任务】 对于所有测试点, • 1 ≤T ≤5, • 2 ≤n ≤15,n −1 ≤m ≤n(n−1) 2 , • ∀1 ≤i ≤m, 1 ≤ui < vi ≤n, 1 ≤wi ≤m, • ∀1 ≤i < j ≤m, (ui, vi)̸ = (uj, vj),即G 没有重边, • 保证G 连通。 测试点编号 n ≤ 特殊性质 1 ∼3 6 A 4 ∼6 15 B 7, 8 9 C 9 ∼11 12 12, 13 14 14 ∼16 15 17, 18 9 无 19, 20 12 21 ∼23 14 24, 25 15 特殊性质A:m ≤6,∀1 ≤i ≤m, wi ≤2。 特殊性质B:∀1 ≤i < j ≤m, wi̸ = wj。 特殊性质C:∀1 ≤i ≤m, wi = 1。 第7 页 共11 页