[USACO] Strongest Friendship Group 题解

· · 题解

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

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

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

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

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

代码