题目详情题解（0）讨论（0）提交记录（0）

AT_icpc2013spring_e.最小生成树

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 nn 个点 mm 条边（n≤105,m≤2×105n\le 10^5,m\le 2\times 10^5）的无向带权图。
求出分别删除每一条边后，最小生成树的权值。无解输出 -1。

输入格式

第一行输入两个数，nn 和 mm。
接下来 mm 行，对于第 i+1i+1 行，输入 ai bi wia_i\ b_i\ w_i，代表一条边连接 ai,bia_i,b_i，边权为 wiw_i。
保证输入的图是简单图，即没有重边和自环。

输出格式

输出 mm 行。
第 ii 行代表删去第 ii 条边后最小生成树的权值。无解输出 -1。

输入输出样例

  • 输入#1

    4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5

    输出#1

    8
6
7
10
6
6

  • 输入#2

    4 4
1 2 1
1 3 10
2 3 100
3 4 1000

    输出#2

    1110
1101
1011
-1

  • 输入#3

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

    输出#3

    27
26
25
29
28
28
28
25
25
25

  • 输入#4

    3 1
1 3 999

    输出#4

    -1

输入解题思路，AI测评打分。不知道怎么写?

首页