H2. 最大化最大连通分量（困难版） – 详细题解

问题描述

给定一个 $n \times m$ 的网格，由 # 和 . 组成。一次操作可以选择一行 $r$ 和一列 $c$，将该行和该列上的所有格子变为 #（无论原来是什么）。求在至多一次操作后，网格中最大的 # 连通分量的大小。

核心思路

操作后，新加入的 # 会出现在整行 $r$ 和整列 $c$ 上（除了交叉点 $(r,c)$ 只算一次）。这些新格子可能会将多个原本分离的 # 连通分量连接起来，也可能与现有的分量合并，形成更大的连通块。我们的目标是最大化这个新连通块的大小。

预处理

1. 首先找出所有初始的 # 连通分量。对每个分量，记录：

   • 大小 $sz$。
   • 它占据的所有行（去重后的列表）。
   • 它占据的所有列（去重后的列表）。

   因为一个连通分量可能分布在多行多列，但任意两个格子通过相邻关系相连，所以分量覆盖的行集和列集是连续的？不一定，但只是为了计算后续的贡献，我们只需要知道哪些行和列上至少有一个该分量的格子。

2. 对于每行 $r$，定义 $R_{\text{sum}}[r] = \sum \{\text{分量大小} \mid \text{该分量占据行 } r\}$。 同理，对于每列 $c$，定义 $C_{\text{sum}}[c] = \sum \{\text{分量大小} \mid \text{该分量占据列 } c\}$。 另外，定义 $A[r][c] = \sum \{\text{分量大小} \mid \text{该分量同时占据行 } r \text{ 和列 } c\}$。

3. 同时统计每行原有的 # 数量 $\text{rowCnt}[r]$，每列原有的 # 数量 $\text{colCnt}[c]$。

操作后的连通块大小计算

假设我们选择行 $r$ 和列 $c$ 进行操作。操作后，所有原来在行 $r$ 或列 $c$ 上的格子都变成了 #。这些新格子与原有的 # 格子（特别是那些与行 $r$ 或列 $c$ 有交的连通分量）会合并成一个大的连通分量。

具体来说，考虑所有与行 $r$ 或 列 $c$ 有交集的初始连通分量。由于操作将行 $r$ 和列 $c$ 全部填满，所有这些分量都会通过这条“十字”连通起来，形成一个大的连通块。此外，行 $r$ 和列 $c$ 上原来不是 # 的格子也会变成 #，它们也属于这个新的大块。

因此，新连通块的大小可以分解为：

• 原有分量贡献：所有与行 $r$ 或列 $c$ 有交的分量的大小之和。
  注意：若一个分量与行 $r$ 和列 $c$ 都有交集，它在求和中会被重复计算一次，需要减去一次。 所以这部分贡献为：

  $$\Bigl(\sum_{\text{分量与行 }r\text{ 有交}} sz\Bigr) \;+\; \Bigl(\sum_{\text{分量与列 }c\text{ 有交}} sz\Bigr) \;-\; \Bigl(\sum_{\text{分量与行 }r\text{ 且与列 }c\text{ 有交}} sz\Bigr) $$

  即：

  $$R_{\text{sum}}[r] + C_{\text{sum}}[c] - A[r][c]$$

• 新增格子贡献：操作将行 $r$ 和列 $c$ 上原本是 . 的格子变成 #。这些格子中的每一个都会直接加入到新的大块中（因为它们与行或列上的 # 相邻）。
  行 $r$ 上原本是 . 的格子有 $m - \text{rowCnt}[r]$ 个；
  列 $c$ 上原本是 . 的格子有 $n - \text{colCnt}[c]$ 个。
  但交叉点 $(r,c)$ 被重复计算了一次，如果它原本是 .，则应该只算一次。因此新增格子总数为：

  $$(m - \text{rowCnt}[r]) + (n - \text{colCnt}[c]) - [\text{grid}[r][c] = '.'] $$

  其中 $[\cdot]$ 是示性函数，当条件成立时为 $1$，否则为 $0$。

因此，选择 $(r,c)$ 后形成的新连通块的大小为：

$$\text{size}(r,c) = R_{\text{sum}}[r] + C_{\text{sum}}[c] - A[r][c] + (m - \text{rowCnt}[r]) + (n - \text{colCnt}[c]) - \delta, $$

其中 $\delta = 1$ 若 $\text{grid}[r][c] = '.'$，否则 $\delta = 0$。

答案

最终答案是所有 $(r,c)$ 对应的 $\text{size}(r,c)$ 以及初始最大连通分量大小三者中的最大值：

$$\text{ans} = \max\left(\max_{id}\text{compSize}[id],\; \max_{1\le r\le n,\;1\le c\le m}\text{size}(r,c)\right). $$

复杂度

• 找出所有连通分量：$O(nm)$，使用 BFS/DFS。
• 统计每行每列的 $R_{\text{sum}}, C_{\text{sum}}, A[r][c]$：$A[r][c]$ 可以通过遍历每个分量，将该分量的大小加到其占据的每一行每一列的交叉点上，总复杂度为 $\sum (\text{行数} \times \text{列数})$，在最坏情况下可能达到 $O(n^2 m^2)$，但每个分量所占的行数和列数通常较小。实际实现时，由于总格子数 $\le 10^6$，每个分量的行数和列数乘积之和不会太大，可以接受。
• 枚举所有 $(r,c)$：$O(nm)$。

总复杂度满足题目限制。

示例验证

以示例第四个测试用例为例（$5\times5$ 网格），通过计算可得最优操作选 $(4,2)$ 得到 $16$，与输出一致。

总结

本题的关键在于理解操作后新连通块的结构：它由所有与选定行或列有交的原有分量，加上新填充的十字上的空格子组成。利用预处理的分量行/列信息，可以 $O(1)$ 计算每个候选操作的结果，从而快速得到最优解。