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 个集合都被【满足】的边集选择方案可能不止一个,所以小宝想问你所有可能的边集选择方案中,被选择边中边权最大的那条边最少得是多少?
(图片来源网络,侵删)