https://www.lydsy.com/JudgeOnline/problem.php?id=4651
https://www.luogu.org/problemnew/show/P1173#sub
这题是一道十分变态的码农分类讨论题。
参考：https://www.cnblogs.com/ljh2000-jump/p/6373541.html
显然答案就四种："-1,0,1,2"。
-1就是只有一个跳蚤或者只有两个相邻的跳蚤。
0就是蛐蛐已经把跳蚤分开了。
1情况思考，我们把相邻的跳蚤连边，如果有割点的话，我们只要在割点处放一个蛐蛐就行了。
剩下的情况就是2了。
然而跳蚤的个数有点多，我们只能拿几个跳蚤出来建图跑tarjan。
一个优秀的方法是拿已放好的蛐蛐为中心5*5的方格内的跳蚤。
（PS：为什么不拿3*3的呢？因为如果蛐蛐在边界上的话有割点那也是假的，为了防止假割点于是在外围再放一层，思考一下。）
查找蛐蛐和跳蚤的坐标用map会奇慢（血的教训*1），所以写哈希表存。
另外，外面一层的跳蚤如果产生割点，同理也是假的，不予理会即可。
然后就是uoj的hack数据了，这里提供些debug数据，仅供参考。
ans： -
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double dl;
const int INF=2e9;
const int N=1e5+;
const int M=N*;
const int P=;
const int B=1e9+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct Hash{
int cnt,head[P],nxt[M];
ll to[M];
inline void init(){
cnt=;memset(head,,sizeof(head));
}
inline void add(ll x,ll y){
ll v=(x*B+y);int u=v%P;
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
inline int qry(ll x,ll y){
ll v=(x*B+y);int u=v%P;
for(int i=head[u];i;i=nxt[i])
if(to[i]==v)return i;
return ;
}
}mp1,mp2;
struct node{
int x,y;
}p[N],q[M];
int im[M],n,m,c;
int DX[]={,,-,};
int DY[]={,,,-};
int dx[]={-,-,-,-,-,-,-,-,-,-,,,,,,,,,,,,,,};
int dy[]={-,-,,,,-,-,,,,-,-,,,-,-,,,,-,-,,,};
inline dl dis(dl x1,dl y1,dl x2,dl y2){
dl x=x1-x2,y=y1-y2;
return sqrt(x*x+y*y);
}
struct edge{
int to,nxt;
}e[M*];
int cnt,head[M],dfn[M],low[M],to[M],id,t,rtson;
bool cut[M];
inline void add(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void tarjan(int u,int f){
to[u]=id;dfn[u]=low[u]=++t;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]&&f)cut[u]=;
if(!f)rtson++;
}else if(f!=v)
low[u]=min(low[u],dfn[v]);
}
if(!f&&rtson>=)cut[u]=;
}
bool vis1[M],vis2[M];
int dui[M],top;
inline void init(){
for(int i=;i<=mp1.cnt;i++)vis2[i]=;
for(int i=;i<=mp2.cnt;i++)cut[i]=head[i]=low[i]=dfn[i]=to[i]=vis1[i]=;
mp1.init();mp2.init();t=cnt=;
}
inline void getnode(int x,int y,int iid){
vis2[iid]=;
for(int i=;i<;i++){
int nx=x+DX[i],ny=y+DY[i];
if(nx<||nx>n||ny<||ny>m)continue;
int nxtid=mp1.qry(nx,ny);
if(nxtid)continue;
int tmp=mp2.qry(nx,ny);
if(vis1[tmp])continue;
vis1[tmp]=;dui[++top]=tmp;
}
for(int i=;i<;i++){
int nx=x+DX[i],ny=y+DY[i];
if(nx<||nx>n||ny<||ny>m)continue;
int nxtid=mp1.qry(nx,ny);
if(nxtid){
if(!vis2[nxtid])getnode(nx,ny,nxtid);
continue;
}
}
for(int i=;i<;i++){
int nx=x+DX[i],ny=y+DY[i];
if(nx<||nx>n||ny<||ny>m)continue;
vis1[mp2.qry(nx,ny)]=;
}
}
inline void solve(){
for(int i=;i<=mp2.cnt;i++)
if(!dfn[i]){
id++;rtson=;tarjan(i,);
}
for(int i=;i<=c;i++){
if(vis2[i])continue;
top=;getnode(p[i].x,p[i].y,i);
for(int j=;j<=top;j++)
if(to[dui[j]]!=to[dui[]]){puts("");return;}
}
if(n==||m==){puts("");return;}
for(int i=;i<=mp2.cnt;i++)
if(cut[i]&&im[i]==){
puts("");return;
}
puts("");
}
inline bool find(){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(!mp1.qry(i,j)){
for(int k=;k<;k++){
int x=i+DX[k],y=j+DY[k];
if(x<||x>n||y<||y>m)continue;
if(!mp1.qry(x,y))return ;
}
return ;
}
}
}
return ;
}
int main(){
int T=read();
while(T--){
init();
n=read(),m=read(),c=read();
for(int i=;i<=c;i++){
p[i].x=read(),p[i].y=read();
mp1.add(p[i].x,p[i].y);
}
if((ll)n*m-c<=||((ll)n*m-c==&&find())){puts("-1");continue;}
for(int i=;i<=c;i++){
int x=p[i].x,y=p[i].y;
for(int j=;j<;j++){
int nx=x+dx[j],ny=y+dy[j];
if(nx<||nx>n||ny<||ny>m||mp1.qry(nx,ny))continue;
int tmp=mp2.qry(nx,ny);
if(!tmp){
mp2.add(nx,ny);
if(dis(x,y,nx,ny)<1.9)im[mp2.cnt]=;
else im[mp2.cnt]=;
q[mp2.cnt]=(node){nx,ny};
}else{
if(dis(x,y,nx,ny)<1.9)im[tmp]=;
else im[tmp]=min(,im[tmp]);
}
}
}
for(int i=;i<=mp2.cnt;i++){
int x=q[i].x,y=q[i].y;
for(int j=;j<;j++){
int nx=x+DX[j],ny=y+DY[j];
if(nx<||nx>n||ny<||ny>m)continue;
int tmp=mp2.qry(nx,ny);
if(tmp&&im[tmp])add(i,tmp);
}
}
solve();
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++