自动搬运

查看原文

来自洛谷，原作者为

	ttq012 **

搬运于2025-08-24 22:16:02，当前版本为作者最后更新于2023-08-27 18:33:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑分类讨论。

首先枚举每一个强连通 $B$ 块。

情况 $1$：

• 任意的一个连通块都无法通过扩展两个点的方式和其他的连通块连通。
• 对于每一个这样的连通块，这个连通块得到的最大贡献是 $s+2$，其中 $s$ 是连通块的大小。

情况 $2$：

• 对于 ABCDEF 组成的连通块而言，可以通过对周围扩展和其他的两个连通块连接，贡献为 $3$ 个连通块的大小的和 $+2$。
• 贪心选择两个最大的连通块即可。

情况 $3$：

• 上述的两个连通块可以通过扩展两个点来连通，贡献为两个连通块的大小 $+2$。

由于 $B$ 部分是矩形，所有矩形的周长的和是 $n^2$ 级别的，所以直接暴力模拟即可。