70104 - 2025青少年编程挑战赛提高组完善2
统计题目(材料题)
扩充最小生成树 给定n个节点一个树，树的每条边有权值。把这个树扩充成完全图，使得完全图的最小生成树一定是原来的树。求扩充的边的权值总和的最小值。
|
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<iostream> #include<algorithm> using namespace std; struct edge { int u, v, val; }el[10001]; int group[10001]; int cnt[10001]; bool cmp(edge e1, edge e2) { return ① ; } int find(int x) { if (x != group[x]) { group[x] = find(group[x]); } return group[x]; } int main() { int n; long long ans = 0; cin >> n; for ( ② ) { cin >> el[i].u >> el[i].v >> el[i].val; } sort(el + 1, el + n, cmp); for (int i = 1; i <= n; i++) { group[i] = i; ③ ; } for (int i = 1; i < n; i++) { int x = find(el[i].u), y = find(el[i].v); ans += ( ④ ) * (el[i].val + 1); ⑤ ; group[x] = group[y]; } cout << ans; } |
关注我们
