70188 - 2025挑战赛Py提高组完善2
统计题目(材料题)
扩充最小生成树 给定n个节点一个树，树的每条边有权值。把这个树扩充成完全图，使得完全图的最小生成树一定是原来的树。求扩充的边的权值总和的最小值。
试补全程序：
01 def main():
02 import sys
03 input = sys.stdin.read
04 data = input().split()
05
06 idx = 0
07 n = int(data[idx])
08 idx += 1
09
10 edges = []
11 for _ in range(n - 1):
12 u = int(data[idx])
13 v = int(data[idx + 1])
14 val = int(data[idx + 2])
15 edges.append((u, v, val))
16 idx += 3
17
18 edges.sort(key= ① )
19
20 group = [i for i in range(n + 1)]
21 cnt = [1] * (n + 1)
22 ans = 0
23
24 for u, v, val in edges:
25 x = find(u, group)
26 y = find(v, group)
27 ②
28 cnt[y] += cnt[x]
29 ③
30
31 print(ans)
32
33 def find(x, group):
34 if ④ :
35 ⑤
36 return group[x]
37
38 if __name__ == "__main__":
39 main()
关注我们
