33OJ
登录 注册

#CF609E. MST for each edge

MST for each edge

题目描述

给定一张 nn 个点、mm 条边的连通带权无向图,点编号为 11 到 nn,边按输入顺序编号为 11 到 mm。

对每条边 ii,求:在所有包含边 ii 的生成树中,边权和的最小值。

输入格式

第一行两个整数 nn、mm。

接下来 mm 行,每行三个整数 uiu_i、viv_i、wiw_i,表示第 ii 条边连接 uiu_i 和 viv_i,边权为 wiw_i。

输出格式

输出 mm 行,第 ii 行一个整数,表示包含第 ii 条边的最小生成树的边权和。

样例

5 7
1 2 1
1 3 1
2 3 1
3 4 1
3 5 1
4 5 1
1 5 2
4
4
4
4
4
4
5
4 5
1 2 2
2 3 3
3 4 1
1 3 5
2 4 4
6
6
6
8
7

样例解释

第一组样例中,前六条边可以组成一棵权值和为 44 的最小生成树,包含其中任意一条时答案都是 44。最后一条边 (1,5,2)(1,5,2) 加入后,需要换掉树上 11 到 55 路径中权值最大的一条边,答案为 4+2−1=54+2-1=5。

第二组样例中,最小生成树是 (1,2,2)(1,2,2)、(2,3,3)(2,3,3)、(3,4,1)(3,4,1),权值和为 66。第 44 条边 (1,3,5)(1,3,5) 加入后,路径最大边为 33,答案为 6+5−3=86+5-3=8;第 55 条边 (2,4,4)(2,4,4) 加入后,路径最大边为 33,答案为 6+4−3=76+4-3=7。

数据范围与约定

子任务 分值 限制
11 3030 2≤n≤1002 \le n \le 100,n−1≤m≤100n-1 \le m \le 100
22 2≤n≤20002 \le n \le 2000,n−1≤m≤2000n-1 \le m \le 2000
33 4040 2≤n≤2×1052 \le n \le 2 \times 10^5,n−1≤m≤2×105n-1 \le m \le 2 \times 10^5,1≤wi≤1091 \le w_i \le 10^9

图保证连通,1≤ui≠vi≤n1 \le u_i \ne v_i \le n,1≤wi≤1091 \le w_i \le 10^9。