4424. [ICPC2026河南省赛]最小生成图

【题目描述】

小 C 最近在研究最小生成树，他灵机一动想出这么一道题：

给定一个 $n$ 个点 $m$ 条边的无向连通图，第 $i$ 条边连接 $u_i$ 号节点和 $v_i$ 号节点，边权为 $w_i$，图中可能存在重边和自环。

小 C 从中取出任意多条边并且以任意顺序将边排列，即构造一个序列 $a_1,a_2,a_3,\cdots,a_k$（$n-1 \le k \le m$，$1 \le a_i \le m$ 且 $a_i$ 互不相同），进行 $k$ 次操作，第 $i$ 次操作选择第 $a_i$ 条边并连接该边对应的两个点 $u_{a_i}$ 和 $v_{a_i}$，此时这条边的代价为 $\frac{w_{a_i}}{i}$ ，总代价为选中的每条边代价的和，求能使 $n$ 个点联通的所有方案中总代价的最小值。

【输入格式】

第一行输入两个整数 $n,m$（$1 \le n \le 3\times 10^3,n-1 \le m \le 5\times 10^3$）

接下来 $m$ 行，每行三个空格隔开的整数 $u_i,v_i,w_i$，表示第 $i$ 条边连接 $u_i$ 号节点和 $v_i$ 号节点且边权为 $w_i$（$1 \le u_i,v_i \le n$，$1 \le w_i \le 10^9$）

【输出格式】

请输出一行一个数表示总代价的最小值，结果四舍五入到整数。

【输入样例】

5 9
1 2 1
2 3 2
1 3 3
2 3 4
1 3 5
1 3 50
1 4 60
1 5 70
4 5 80

【输出样例】

25

【样例说明】

依次选择第 $1,2,3,4,5,7,8$ 条边，此时总代价最小，为 $\frac{1}{1} + \frac{2}{2} + \frac{3}{3} + \frac{4}{4} + \frac{5}{5} + \frac{60}{6} + \frac{70}{7} =25$

【来源】

ICPC 2026 河南省赛。