给定一个连通的无向图N节点 (1 NN-1边缘。我们定义一个函数F(a,b), where F(a, b)等于路径中的最大边权重a to b。我们如何找到总和F(a, b)对全部a, b这样1 <= a, b <= N（模 10^9 + 7）
示例图
F(a,b)等于从a到b的路径中的最大边权重。
F(1, 2) = 2
F(1, 3) = 2
F(1, 4) = 4
F(1, 5) = 4
F(2, 3) = 1
F(2, 4) = 4
F(2, 5) = 4
F(3, 4) = 4
F(3, 5) = 4
F(4, 5) = 3
所有对的 F 之和等于 32。
为此，我们可以使用 Kruskal 的 MST 算法的变体（Kruskal 通过增加权重对边进行排序，借助不相交集数据结构贪婪地插入不形成循环的边）。将运行总和初始化为零；每当我们通过权重 w 的边将大小为 S1 的不相交集（此信息可作为按大小并集的不相交集数据结构的副产品）与大小为 S2 的不相交集合并时，将 S1*S2*w 添加到总和模 10^9 + 7。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
