原文链接www.cnblogs.com/zhouzhendong/p/UOJ220.html

前言

真是一道翔题。

草率题解

-1 的情况很好判，只有两种情况： n * m - c < 2 或者 n * m - c = 2 且两个格子相邻。

对于 x 坐标，我们大力将前两行、后两行、每一个点的上一行、所在行、下一行这些行离散化出来。

对于每一行，我们找出一些关键点，将一行分为若干段，将每一段看做一个点，上下左右相邻的段连边，跑Tarjan判割点。

怎么找关键点？对于每一个点，它左右距离2范围内，上下距离1 范围内的都拿出来就好了。

常数真大。

代码

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof x)

#define For(i,a,b) for (int i=(a);i<=(b);i++)

#define Fod(i,b,a) for (int i=(b);i>=(a);i--)

#define fi first

#define se second

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

#define outval(x) cerr<<#x" = "<<x<<endl

#define outtag(x) cerr<<"---------------"#x"---------------"<<endl

#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\

						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef vector <int> vi;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=100010;

int T,n,m,c,s;

map <pair <int,int>,int> g;

int x[N],xx[N],y[N];

int dx[4]={ 0, 0, 1,-1};

int dy[4]={ 1,-1, 0, 0};

int Hx[N*3],cx,sum[N*3];

vector <int> Hy[N*3];

const int S=N*30;

vector <int> e[S];

int co[S];

void Add_Edge(int x,int y){

	if (!co[x]&&!co[y])

		e[x].pb(y),e[y].pb(x);

}

int dfn[S],low[S],Time;

int flag,cntroot=0,fir;

void Tarjan(int x,int pre){

	dfn[x]=low[x]=++Time;

	for (auto y : e[x])

		if (!dfn[y]){

			Tarjan(y,x);

			low[x]=min(low[x],low[y]);

			if (low[y]>=dfn[x]){

				if (pre)

					flag=1;

				else

					cntroot++;

			}

		}

		else if (y!=pre)

			low[x]=min(low[x],dfn[y]);

}

bool check1(int x,int y){

	return 1<=x&&x<=n&&1<=y&&y<=m;

}

void Solve(){

	n=read(),m=read(),c=read();

	g.clear();

	For(i,1,c){

		x[i]=read(),y[i]=read();

		g[mp(x[i],y[i])]=1;

	}

	if ((LL)n*m-c<=1)

		return (void)puts("-1");

	if ((LL)n*m-c==2){

		For(i,1,n)

			For(j,1,m)

				if (!g[mp(i,j)])

					For(k,0,3)

						if (check1(i+dx[k],j+dy[k])&&!g[mp(i+dx[k],j+dy[k])])

							return (void)puts("-1");

		return (void)puts("0");

	}

	cx=0;

	For(i,1,c){

		if (x[i]>1)

			Hx[++cx]=x[i]-1;

		Hx[++cx]=x[i];

		if (x[i]<n)

			Hx[++cx]=x[i]+1;

	}

	Hx[++cx]=1,Hx[++cx]=n;

	if (n>1)

		Hx[++cx]=2,Hx[++cx]=n-1;

	sort(Hx+1,Hx+cx+1);

	cx=unique(Hx+1,Hx+cx+1)-Hx-1;

	For(i,1,cx)

		Hy[i].clear();

	For(i,1,c){

		xx[i]=lower_bound(Hx+1,Hx+cx+1,x[i])-Hx;

		For(xp,xx[i]-1,xx[i]+1){

			if (xp<1||xp>n)

				continue;

			For(yp,y[i]-1,y[i]+2)

				if (1<=yp&&yp<=m)

					Hy[xp].pb(yp);

		}

	}

	sum[0]=1;

	For(i,1,cx){

		Hy[i].pb(1),Hy[i].pb(2),Hy[i].pb(m+1),Hy[i].pb(m);

		sort(Hy[i].begin(),Hy[i].end());

		Hy[i].resize(unique(Hy[i].begin(),Hy[i].end())-Hy[i].begin());

		For(j,0,(int)Hy[i].size()-2)

			co[sum[i-1]+j]=g[mp(Hx[i],Hy[i][j])];

		sum[i]=sum[i-1]+(int)Hy[i].size()-1;

	}

	s=sum[cx]-1;

	For(i,1,s)

		e[i].clear();

	For(i,1,cx)

		For(j,0,(int)Hy[i].size()-3)

			Add_Edge(sum[i-1]+j,sum[i-1]+j+1);

	For(i,2,cx){

		int p=0;

		for (int j=0;j<=(int)Hy[i].size()-2;j++){

			while (Hy[i-1][p+1]<=Hy[i][j])

				p++;

			while (p<(int)Hy[i-1].size()-1&&Hy[i-1][p+1]<=Hy[i][j+1]){

				Add_Edge(sum[i-2]+p,sum[i-1]+j);

				p++;

			}

			if (Hy[i-1][p]<Hy[i][j+1])

				Add_Edge(sum[i-2]+p,sum[i-1]+j);

		}

	}

	clr(dfn),clr(low);

	fir=Time=flag=cntroot=0;

	For(i,1,s){

		if (co[i]||dfn[i])

			continue;

		if (!fir)

			fir=i;

		if (!dfn[i]&&i!=fir)

			return (void)puts("0");

		Tarjan(i,0);

	}

	flag|=cntroot>1;

	puts(flag?"1":"2");

}

int main(){

	T=read();

	while (T--)

		Solve();

	return 0;

}

巴特西

UOJ#220. 【NOI2016】网格 Tarjan

前言

草率题解

代码

最新文章

热门文章