NOI2016 网格（Tarjan求割点）

发表于 |
字数统计: 1,963字 | 阅读时长 ≈ 10min

【NOI2016】网格

问题描述

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

他们在一个 $n$ 行 $m$ 列的网格上排兵布阵。其中的 $c$ 个格子中 $(0 \leq c \leq nm)$，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。

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

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

现在，蛐蛐国王希望，将某些（零个，一个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。

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

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

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

输入格式

每个输入文件包含多组数据。
输入文件的第一行只有一个整数 $T$，表示数据的组数。
接下来依次输入 $T$ 组数据，每组数据的第一行包含三个整数 $n, m, c$。
接下来 $c$ 行，每行包含两个整数 $x, y$ 表示第 $x$ 行，第 $y$ 列的格子被一个蛐蛐占据。每一组数据当中，同一个蛐蛐不会被多次描述。
同一行相邻的整数之间由一个空格隔开。

输出格式

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

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

样例输入

4
4 4 2
1 1
4 4
2 3 1
1 2
2 2 2
1 1
2 2
1 1 0

样例输出

2
1
0
-1

提示

对于所有的数据，$1 \leq n,m \leq 10^9, \ 0 \leq c \leq \text{min}(nm,10^5),\ 1 \leq x \leq n,\ 1 \leq y \leq m,\ 1 \leq T \leq 20$。

我们记 $\sum c$ 为某个测试点中，其 $T$ 组输入数据的所有 $c$ 的总和，则保证 $\sum c≤10^5$。

这题乍一看感觉很麻烦，但思索一下就能发现答案显然只可能是$-1,0,1,2$之一。考虑依次判断。

容易发现答案为$-1$当且仅当图中跳蚤数量小于二，或跳蚤数量等于二且相邻。

否则答案为$0$当且仅当原图中存在至少两只不连通的跳蚤。

否则答案为$1$当且仅当图中存在割点，否则答案为$2$

然后发现棋盘很大，不可能把完整的图建出来，考虑只把关键点拿出来讨论。

容易发现可能成为割点的点只可能是障碍格子八连通的点，考虑只将这些点拿出来，但容易发现当有一个障碍在棋盘边缘时，这样做会出问题，那么考虑再往外拓展一圈，即拿出24个点来。

然后只需要跑个Tarjan求割点就行了。注意到判断答案是否为$0$只需要将八连通的障碍合并后讨论它相邻的格子就行了。

最后需要注意，上面的建图还是有反例，就是当两个障碍刚好在对角，且中间有三个格子时。

这个只需要最后判断割点八连通格子中是否有障碍就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<vector>
#define ll long long
#define N 3000233
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
typedef pair<int,int> par;
const int mul=1e9+1;
const int dx4[4]={1,-1,0,0},dy4[4]={0,0,1,-1};
const int dx8[8]={1,0,-1,1,-1,1,0,-1},dy8[8]={-1,-1,-1,0,0,1,1,1};
int T,n,m,c,bel[N],Bel;bool ex_cp,cut[N];
vector<par>P,Q;
vector<int>around[N],G[N];
int cnt,dfn[N],low[N],be[N],scc,VT;
bool valid(int x,int y){return x<=n&&y<=m&&x>0&&y>0;}
struct Hash_table
{
	const static int MOD=666666;
	int tot,las[MOD],nex[N],val[N],stx[N],sty[N];
	void clear()
	{
		tot=0;memset(las,0,sizeof(las));
	}
	void ins(int x,int y,int k)
	{
		int p=(1ll*x*mul+y)%MOD,i;
		val[++tot]=k;
		stx[tot]=x;sty[tot]=y;
		nex[tot]=las[p];
		las[p]=tot;
	}
	int find(int x,int y)
	{
		int p=(1ll*x*mul+y)%MOD,i;
		for(i=las[p];i;i=nex[i])if(stx[i]==x&&sty[i]==y)return val[i];
		return -1;
	}
}A,B;
void Tarjan(int x,int fa)
{
	int i,y,son=0;
	dfn[x]=low[x]=++VT;be[x]=scc;
	for(i=0;i<G[x].size();i++)
	{
		y=G[x][i];if(y==fa)continue;
		if(!dfn[y])
		{
			Tarjan(y,x);son++;
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y])cut[x]=1;
		}
		else low[x]=min(dfn[y],low[x]);
	}
	if(fa==0&&son==1)cut[x]=0;
}
void find_bel(int x,int y,int lab)
{
	bel[lab]=Bel;
	int i,tx,ty,p;
	for(i=0;i<8;i++)
	{
		tx=dx8[i]+x;ty=dy8[i]+y;
		p=A.find(tx,ty);
		if(p!=-1&&bel[p]==0)find_bel(tx,ty,p);
	}
}
bool Connect()
{
	int i,k,x,y,tx,ty,dx,dy,p,q;
	for(i=0;i<c;i++)A.ins(P[i].first,P[i].second,i);
	for(i=0;i<c;i++)
	if(bel[i]==0)
	{
		Bel++;
		find_bel(P[i].first,P[i].second,i);
	}
	for(i=1;i<=Bel;i++)around[i].clear();
	for(i=0;i<c;i++)
	{
		x=P[i].first;y=P[i].second;
		for(dx=-2;dx<=2;dx++)
		for(dy=-2;dy<=2;dy++)
		if(dx||dy)
		{
			tx=dx+x;ty=dy+y;
			if(!valid(tx,ty))continue;
			if(A.find(tx,ty)!=-1||B.find(tx,ty)!=-1)continue;
			cnt++;
			Q.push_back(par(tx,ty));
			around[bel[i]].push_back(cnt);
			B.ins(tx,ty,cnt);
		}
	}
	for(i=1;i<=cnt;i++)G[i].clear();
	for(i=0;i<cnt;i++)
	{
		x=Q[i].first;y=Q[i].second;p=i+1;
		for(k=0;k<4;k++)
		{
			tx=x+dx4[k];
			ty=y+dy4[k];
			q=B.find(tx,ty);
			if(q!=-1)G[p].push_back(q);
		}
	}
	fill(dfn,dfn+cnt+1,0);
	fill(low,low+cnt+1,0);
	fill(be,be+cnt+1,0);
	fill(cut,cut+cnt+1,0);
	for(i=1;i<=cnt;i++)if(be[i]==0)scc++,Tarjan(i,0);
	for(i=0;i<cnt;i++)
	if(cut[i+1])
	{
		x=Q[i].first;y=Q[i].second;
		for(k=0;k<8;k++)
		{
			tx=x+dx8[k];
			ty=y+dy8[k];
			if(A.find(tx,ty)!=-1)ex_cp=1;
		}
	}
	for(i=1;i<=Bel;i++)
	{
		p=-1;
		for(k=0;k<around[i].size();k++)
		{
			if(p==-1)p=be[around[i][k]];
			else if(be[around[i][k]]!=p)return 0;
		}
	}
	return 1;
}
void Clear()
{
	P.clear();Q.clear();
	A.clear();B.clear();
	fill(bel,bel+c+1,0);
	Bel=cnt=scc=VT=ex_cp=0;
}
int tmain()
{
	int T;_R(T);
	while(T--)
	{
		int i,x,y;
		_R(n);_R(m);_R(c);
		Clear();
		for(i=1;i<=c;i++)
		{
			_R(x);_R(y);
			P.push_back(par(x,y));
		}
		if((ll)n*m-c<2ll){puts("-1");continue;}
		if(!Connect()){puts("0");continue;}
		if((ll)n*m-c==2ll)
		{
			if(scc==1||!c)puts("-1");
			else puts("0");continue;
		}
		if(ex_cp||n==1||m==1)puts("1");
		else puts("2");
	}
}
const int main_stack=16; 
char my_stack[128<<20]; 
int main() { 
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory"); 
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp"); 
  tmain(); 
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp"); 
}