BZOJ 4423 【AMPPZ2013】 Bytehattan

Description

比特哈顿镇有n*n个格点，形成了一个网格图。一开始整张图是完整的。
有k次操作，每次会删掉图中的一条边(u,v)，你需要回答在删除这条边之后u和v是否仍然连通。

Input

第一行包含两个正整数n,k(2<=n<=1500,1<=k<=2n(n-1))，表示网格图的大小以及操作的个数。
接下来k行，每行包含两条信息，每条信息包含两个正整数a,b(1<=a,b<=n)以及一个字符c(c=N或者E)。
如果c=N，表示删除(a,b)到(a,b+1)这条边；如果c=E，表示删除(a,b)到(a+1,b)这条边。
数据进行了加密，对于每个操作，如果上一个询问回答为TAK或者这是第一个操作，那么只考虑第一条信息，否则只考虑第二条信息。
数据保证每条边最多被删除一次。

Output

输出k行，对于每个询问，如果仍然连通，输出TAK，否则输出NIE。

　　这道题一开始想了很久不会做，后来膜了大神的题解后发现了一个神奇的性质，然后就可以做了。

　　删除一条边可以看做把两个空块联通。当删除一条边时这条边连接的两个空块已经联通了，那么删除这条边会导致这条边的两个顶点不联通。

　　仔细想想觉得非常有道理。当删除一条边时发现这条边连接的两个空块已经联通了，那么删除这条边后会出现一个空块连成的环，于是就把里面的点和外面的点给隔开了。

　　之后的事就非常简单了。将空块抠出来(其实就是对偶图不连边)，然后并查集维护联通性即可。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define N 1510

using namespace std;

typedef long long llg;

int n,k,fa[N*N],w[N][N];

bool ans;

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

int find(int x){return fa[fa[x]]==fa[x]?fa[x]:fa[x]=find(fa[x]);}

int main(){

	File("a");

	n=getint(); k=getint(); int S=(n-1)*(n-1)+1;

	for(int i=1;i<=n*n;i++) fa[i]=i;

	for(int i=0;i<=n;i++)

		for(int j=0;j<=n;j++) w[i][j]=S;

	for(int i=1,now=0;i<n;i++)

		for(int j=1;j<n;j++) w[i][j]=++now;

	while(k--){

		int a=getint(),aa,b=getint(),bb;

		char c=getchar(),cc;

		while(c!='N' && c!='E') c=getchar();

		aa=getint(),bb=getint();cc=getchar();

		while(cc!='N' && cc!='E') cc=getchar();

		if(ans) a=aa,b=bb,c=cc;

		int l,r;

		if(c=='E') l=w[a][b],r=w[a][b-1];

		else l=w[a][b],r=w[a-1][b];

		ans=(find(l)==find(r));

		if(!ans) fa[find(l)]=find(r);

		printf(ans?"NIE\n":"TAK\n");

	}

	return 0;

}

巴特西

BZOJ 4423 【AMPPZ2013】 Bytehattan

Description

Input

Output

最新文章

热门文章