一张图,每条边有两个属性 (gi,si)(g_i, s_i)(gi,si) 。给定 G,SG, SG,S,求一棵图的生成树 TTT,使得 G×max(gi)+S×max(si)G \times \max(g_i) + S \times \max (s_i)G×max(gi)+S×max(si) 最小 (i∈T)(i\in T)(i∈T)。
Tips:\operatorname{Tips:}Tips: 图可能包含重边和自环。
一张图,每条边有两个属性 $(g_i, s_i)$ 。给定 $G, S$,求一棵图的生成树 $T$,使得 $G \times \max(g_i) + S \times \max (s_i)$ 最小 $(i\in T)$。 $\operatorname{Tips:}$ 图可能包含重边和自环。