06605. GESP-8级-2025-09-最小生成树

题目描述

给定一张包含 $n$ 个结点 $m$ 条边的带权连通无向图，结点依次以 $1, 2, \dots, n$ 编号，第 $i$ 条边（ $1 \leq i \leq m$ ）连接结点 $u_{i}$ 与结点 $v_{i}$ ，边权为 $w_{i}$ 。

对于每条边，请你求出从图中移除该条边后，图的最小生成树中所有边的边权和。特别地，若移除某条边后图的最小生成树不存在，则输出 $- 1$ 。

请注意，数据可能存在重边。

第一行，两个正整数 $n, m$ ，分别表示图的结点数与边数。

接下来 $m$ 行中的第 $i$ 行（ $1 \leq i \leq m$ ）包含三个正整数 $u_{i}, v_{i}, w_{i}$ ，表示图中连接结点 $u_{i}$ 与结点 $v_{i}$ 的边，边权为 $w_{i}$ 。

输出共 $m$ 行，第 $i$ 行（ $1 \leq i \leq m$ ）包含一个整数，表示移除第 $i$ 条边后，图的最小生成树中所有边的边权和。若移除第 $i$ 条边后图的最小生成树不存在，则输出 $- 1$ 。

输入

输出

::cute-table{tuack}

子任务编号	测试点占比	$n$	$m$	特殊性质
1	$20%$	$\leq 50$	$\leq 100$	-
2	$30%$	$\leq 1 0^{5}$	$\leq 1 0^{5}$	$n = m$
3	$30%$	$\leq 500$	$\leq 2 \times 1 0^{4}$	-
4	$20%$	$\leq 1 0^{5}$	$\leq 1 0^{5}$	-

对于所有测试点，保证 $1 \leq n \leq 1 0^{5}$ ， $1 \leq m \leq 1 0^{5}$ ， $1 \leq u_{i}, v_{i} \leq n$ ， $1 \leq w_{i} \leq 1 0^{9}$ 。

来源：洛谷 P14080（CCF GESP 8 级上机题）