AC. 梦想

frank_c1

[NOI 2016] 网格

发布于2016年08月06日 | 暂无评论 | 1,225阅读 | 图论,搜索,贪心

题目描述

跳蚤国王和蛐蛐国王在玩一个游戏。

他们在一个nm列的网格上排兵布阵。其中的c个格子中(0 \le c \le nm),每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。

我们称占据的格子有公共边的两只跳蚤是相邻的。

我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,或存在另一只跳蚤与这两只跳蚤都连通。

现在,蛐蛐国王希望,将某些(0个,1个或多个)跳蚤替换成蛐蛐,使得在此之后存在至少两只跳蚤不连通。

例如:我们用图左表示一只跳蚤,用图右表示一只蛐蛐,那么图1描述了一个n = 4, m = 4, c = 2的情况。

2016080601

这种情况下蛐蛐国王可以通过将第2行第2列,和第3行第3列的两只跳蚤替换为蛐蛐,从而达成他的希望,如图2所示。并且,不存在更优的方案,但是可能存在其他替换2只跳蚤的方案。

你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成,你还需要最小化被替换的跳蚤的个数。

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数T,表示数据的组数。保证1 \le T \le 20

接下来依次输入T组数据,每组数据的第一行包含三个整数n,m,c。保证1 \le n,m \le 10 ^ 9, 0 \le c \le \min(nm, 10 ^ 5)

接下来c行,每行包含两个整数x,y,表示第x行,第y列的格子被一个蛐蛐占据(1 \le x \le n, 1 \le y \le m)。每一组数据当中,同一个蛐蛐不会被多次描述。

同一行相邻的整数之间由一个空格隔开。

输出格式

对于每一组数据依次输出一行答案。

如果这组数据中,蛐蛐国王的希望不能被达成,输出-1。否则,输出被替换的跳蚤的个数的最小值。

题目解析

说实话,我真的很佩服那些在考场上能把这题AC的爷爷们。这种大分类讨论题,居然有人能绕开所有坑。

在同步赛考场上,我乱写了一个做法交上去居然还有56分真感动。(大概是因为特判了n = 1m = 1

言归正传。我们来讨论一下正解。

方便起见,我们把跳蚤格子称为白格,蛐蛐格子称为黑格。

首先,我们可以发现,如果有解,答案总是不会超过2的。因为我们总能在网格中找到一个角。

于是我们先判断有没有解。显然,如果网格中白格少于2个,肯定是无解的。如果白格恰好有2个,如果它们是四连通意义下相邻的,也是无解的。否则,一定有解。

如果确定了有解,我们只需要确定答案能否为0或1。

在此之前,我们先特判n = 1m = 1的情况。

考虑为0的情况,即白格是不连通的。什么情况下可能不连通呢?我们发现,如果要让白格不连通,一定是一些黑格组成的八连通分量把某些白格围在了内部。由于黑格数量不多,我们可以枚举所有黑格的八连通分量,对其周围的白格DFS一波就好了。但是我们DFS所有白格是O(nm)的,考虑优化。

注意到与黑格八连通的白格才有用,其他白格其实是没有意义的。于是我们预处理这些格子,DFS时只走这些格子即可。

再来考虑1的情况,即我们加一个黑格即可把某些白格围住,就像一个环上的缺口。如果我们把所有白格在四连通意义下抽象成一个图,可以发现这样的白格其实是这个图的割点。于是问题转化成了求图是否有割点。求所有白格的割点是O(nm)的,考虑优化。

注意到如果有割点,这个割点一定是与某个黑格八连通意义下相邻的。于是所有与某个黑格八连通意义下相邻的白格是要加入图中的。但是如果只搜这些白格,原来不是割点的格子可能就变成割点了。于是与这些白格八连通的白格也要加入图中,但是这些格子不能成为割点。于是再对这些白格DFS一波就好了。

判断白格是否在图中可以用哈希或map实现。如果用哈希,时间复杂度是O(Tc)

这题写起来简直了…… 一言不合就5K。