HBC252737Game最便宜的构建题解

你曾走过我的故事 算法基础篇 34 0
全网最全C++题库,助您快速提升编程技能!题库丰富多样,涵盖各个领域,让您在练习中不断成长!
k 个集合都被,一个集合被当且仅当集合中结点编号所代表的结点在子图上是连通的,k 个集合都被的边集选择方案可能不止一个,所以小宝想问你所有可能的边集选择方案中,被选择边中边权最大的那条边最少得是多少?

有一天,小宝获得了一张 n n 个结点 m m 条边的无向连通图,其中每条边都有边权,第 i i 条边的边权记为 w_i w i ​ 。 牛妹想考一考小宝,她选择了 k k 个关于结点的集合,第 i i 个集合中有 s_i s i ​ 个结点编号,这 s_i s i ​ 个结点编号分别记为: q_{i,1},q_{i,2},...,q_{i,s_i} q i,1 ​ ,q i,2 ​ ,...,q i,s i ​ ​ 。 牛妹让小宝在图的 m m 条边中选择一个子集构成一个子图,使得牛妹选择的 k k 个集合都被【满足】,一个集合被【满足】当且仅当集合中结点编号所代表的结点在子图上是连通的。 显然能够使得  k k 个集合都被【满足】的边集选择方案可能不止一个,所以小宝想问你所有可能的边集选择方案中,被选择边中边权最大的那条边最少得是多少?

HBC252737Game最便宜的构建题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断学习,不断挑战,才能在编程领域中脱颖而出!全网最全C++题库,助您成为编程高手!

标签: HBC252737Game最便宜的构建题解