← 返回题目
题库练习 最小生成树
← 上一题 下一题 →

A71934 | 最小生成树

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

给定一张包含 n 个结点、 m 条边的带权连通无向图。结点依次以 1, 2, \dots, n 编号。第 i 条边（ 1 \le i \le m ）连接结点 u_i 与结点 v_i ，边权为 w_i 。

对于每条边，请你求出从图中移除该条边后，图的最小生成树中所有边的边权和。

特别地，若移除某条边后图的最小生成树不存在，则输出 -1。

输入格式

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

接下来 m 行，第 i 行（ 1 \le i \le m ）包含三个正整数 u_i, v_i, w_i ，表示图中连接结点 u_i 与结点 v_i 的边，边权为 w_i 。

输出格式

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

输入输出样例

输入 #1
5 5
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8
输出 #1
14
15
-1
-1
10
输入 #2
6 10
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6
输出 #2
15
16
17
-1
15
17
18
15
15
15
C++ 编辑器
输入
输出