题解：AT_arc119_d [ARC119D] Grid Repainting 3

· · 题解

[ARC119D] Grid Repainting 3

很有参考价值的构造题。

类似于 [ZJOI2007] 矩阵游戏 的想法，把每一行和每一列建一个点，对于一个为 R 的位置 (i,j) 将 i 和 j+n 连边，那么一次操作就相当于选择一个存在相连的边的点将其边删去，并将该行/列全部变成白色。

首先对于一个连通块，我们可以求出其任意一颗生成树，然后从叶子开始一个一个删点。对于一条边，，如果深度大的那个点代表行就说明染白了一个行，同理深度大的点代表列就说明染白了一个列。这样在我们最多只会留下来一个位置没有被删，一定是最优的。

由于图是二分图，所以只要一个连通块点数大于 1 那么其一定存在保留一个代表行的点和保留一个代表列的点的方案。所以我们只需要知道保留了多少个行和多少个列即可，这一部分可以枚举确定。

构造直接按照上述的 dfs 方法构造即可，总时间复杂度 \operatorname{O}(nm)。