图论、贪心、最小生成树、并查集
断边的代价等于总边权减去保留的边的总权值，最小化断边代价即使保留的边权值最大。
将边按照边权从大到小排序后枚举，如果两个联通块中都存在关键点则跳过该边并将边权计入答案，否则合并这条边连接的两个联通块。
正确性证明：假设当前的选择最优，考虑加入一条边带来的影响。
在联通块内加边显然不劣，在联通块之间加边会导致两个联通块连通，由于使两个联通块连通的只可能是一条边并且当前边边权比以后枚举到的边都更大，操作不劣。
最后修改：2024 年 05 月 26 日
© 允许规范转载