题目描述

小红拿到了一个无向图，她准备副除若干条边，使得最终怡好有2个连通块。小红每次副除一条边后可以获得这条边边权的价值，现在小红想知道自己能获得的最大价值是多少?

输入描述

第一行输入两个整数$n,m$，代表节点数量和边的数量。

题目思路

本题需要前置知识最小生成树。首先判断连通块数量可以通过并查集的方法。考虑连通块为2和1的情况：

1. 连通块数量为2时，此时恰好有两个连通块，所以只需要维护目前的连通块数量，无向图保持连通的最小情况为树，所以等价于求每个连通块的最小生成树，求出生成树后累计边权值，用总边权值减去生成树的边权值即为答案。
2. 连通块数量为1时，此时只有一个连通块，同样考虑构建最小生成树，在最小生成树上去除一条边后即可以分为两个连通块，所以只需要找到最小生成树上的最大边权值减去即可。不存在会比这个方法更优的解法，反证法，假设有两棵树通过一条非常大的边连接，去除这个边之后总的边权会比最小生成树去除最大边权的总边权更小，然而我们考虑最小生成树的过程，我们完全可以改变边的遍历顺序将这两棵树的边先进行合并，所以这种情况的两棵树的权值之和也一定等于总的最小生成树分裂成对应两个子树的权值之和，所以这种情况不会比直接求最小生成树去除最大边更优。

时间复杂度为Kruskal算法的时间复杂度$O(mlogm)$。

代码