P5964

Windy_YY · 2023-08-27 18:33:40 · 题解

考虑分类讨论。

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

情况 1：

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

情况 2：

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

情况 3：

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

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