🟩 Kruskal-4 🧮《删掉最差的线》

（练 “总权 − MST” 的对偶思维：最大可删权值）

题目背景

学院的局域网有很多冗余线路，会形成回路。 为了避免数据在回路里打转，加菲老师要删除一些线，使网络无环且仍连通（即变成生成树）。 由于某些线“很差”（权值代表“问题程度”），老师希望删掉的问题程度总和尽可能大。

题目描述

给定无向连通图，边权 $w$ 表示“问题程度”（越大越应该删）。 你需要删除一些边，使剩余图仍连通且无环（生成树），并让删掉的边权和最大。 输出这个最大值。

等价式： 设总边权和为 $S$，MST（按权最小）总权为 $T$，答案为 $S-T$。

输入格式

第一行 $n,m$。 接下来 $m$ 行：$u,v,w$。保证原图连通。

输出格式

输出一个整数：最大可删权值和。

数据范围

• $1 \le n \le 2\times 10^5$
• $0 \le m \le 3\times 10^5$
• $1 \le w \le 10^9$
• 允许重边
• 允许自环（自环对答案无贡献，应被忽略）

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

106

解释： 总和 $S=3+4+5+100+6=118$。 MST 总权 $T=12$。答案 $S-T=106$。

3 3
1 2 1
2 3 1
1 3 1

1

解释： 总和 3，MST=2，删掉 1。