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

AT_past202004_o.可変全域木

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

给定一张 nn 点（编号 11 到 nn）mm 边（编号 11 到 mm）的简单联通无向图，边 ii 连接顶点 aia_i 和 bib_i，边权为 cic_i。

对于从 11 到 mm 的每条边，找出包含该边且权重最小的生成树，并输出其权重（输入输出样例 #3 证明了结果可能会爆int）。

输入格式

第一行：n,mn,m

接下来 mm 行：第 ii 行为 ai,bi,cia_i,b_i,c_i

输出格式

mm 行，第 ii 行输出包含边 ii 的最小权重生成树的权重。

约束

2≤n≤1052 \le n\le 10^5

n−1≤m≤min⁡(105,n(n−1)/2)n-1 \le m \le \min(10^5,n(n-1)/2)

1≤ai,bi≤n1 \le a_i,b_i \le n

ai≠bia_i \neq b_i

1≤ci≤1091 \le c_i \le 10^9

输入输出样例

  • 输入#1

    3 3
1 2 2
2 3 5
3 1 3

    输出#1

    5
7
5

  • 输入#2

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

    输出#2

    20
21
19
19
19
21
19

  • 输入#3

    8 10
1 2 314159265
2 3 358979323
3 4 846264338
1 3 327950288
1 4 419716939
2 4 937510582
1 5 97494459
1 6 230781640
1 7 628620899
1 8 862803482

    输出#3

    2881526972
2912556007
3308074371
2881526972
2881526972
3399320615
2881526972
2881526972
2881526972
2881526972

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

首页