自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:43:36，当前版本为作者最后更新于2022-12-26 20:16:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接

首先直接求肯定很难做，指数级做法不说还很难优化。考虑换一个角度，一个比较常见的想法就是从特殊的小团体入手。

将奶牛间的朋友关系看作一幅无向图，我们令点 $u$ 为度数最小的点（有很多点的情况下任意取一个），让我们首先考虑所有包含点 $u$ 的点集中最优的一个。这里给出结论：包含点 $u$ 的极大联通子图便是所有包含点 $u$ 的点集中最优的一个。证明的话考虑小团体强度的构成因素，不难发现在所有包含点 $u$ 的点集中，点数当然是此时取到最大，而由于点 $u$ 本身便是度数最小的点，所以此时度数最小点度数也取到最大，因此小团体强度取到最大，证明完毕。

有了上面那个结论，我们就不难得到以下做法：每次取出当前度数最小的点，计算包含其的极大联通子图的答案，再将当前点及其相关边删去，反复操作直至所有点被删完。

思考实现以上操作需要什么：我们需要动态维护度数最小点及其度数，已经其所在极大联通子图的点数。前面两点可以用一个优先队列维护，每删一个点就动态维护与其相邻点的信息，关键是后者。发现直接做并查集无法实现删边操作，考虑先正序求出前者时同时记录删点顺序，再倒序并查集加点，得到想要的信息。

于是这道题就完成了。时间复杂度 $O((n+m)(\log n + \alpha(n)))$。

代码