首页 > 代码库 > BZOJ4423 [AMPPZ2013]Bytehattan

BZOJ4423 [AMPPZ2013]Bytehattan

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

 

 

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

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。

Sample Input

3 4
2 1 E 1 2 N
2 1 N 1 1 N
3 1 N 2 1 N
2 2 N 1 1 N

Sample Output

TAK
TAK
NIE
NIE

 

正解:对偶图+并查集

解题报告:

  这道题的思路很巧妙,不失为一种对偶图的灵活运用。

  考虑如果没有强制在线的话,直接逆序加边、并查集维护即可。而题目要求强制在线,那么我们需要另辟蹊径(其实做法也是一样的......)。

  不妨做出原图的对偶图,每条边对应原图中的一条边,那么可以发现当我处理到某一条边时,如果在对偶图中这条边的对应边连接的两个点(在原图中就是两个面)已经连通了,说明这次删边之后会导致不连通(仔细画画图想想就会发现很有道理);

  否则就在并查集中合并即可。所以实现的话就是变删边为加边,同时并查集维护。注意一个细节:原图是水平的话,那么在对偶图中这条边就应该是竖直的。

 

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 1511; 
const int MAXM = 2500011; 
int n,k,a[MAXN][MAXN],father[MAXM],ans,cnt;
char ch[12];
inline void print(){ if(ans==1) printf("TAK\n"); else printf("NIE\n"); }
inline int find(int x){ if(father[x]!=x) father[x]=find(father[x]); return father[x]; }
inline void solve(int x,int y){
	int r1,r2; 
	if(ch[0]==‘E‘) { r1=find(a[x][y-1]); r2=find(a[x][y]);  }
	else { r1=find(a[x-1][y]); r2=find(a[x][y]);  }	
	if(r1!=r2) father[r1]=r2,ans=1; else ans=0;
	print();
}

inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline void work(){
	n=getint(); k=getint(); n--; int lim=n*n; for(int i=1;i<=lim;i++) father[i]=i; ans=1; int x,y;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=++cnt;
	while(k--) {
		x=getint(); y=getint();	scanf("%s",ch);
		if(ans==1) { solve(x,y); x=getint(); y=getint(); scanf("%s",ch); }
		else {	x=getint(); y=getint(); scanf("%s",ch);	solve(x,y);	}   
	}
}

int main()
{
    work();
    return 0;
}

  

BZOJ4423 [AMPPZ2013]Bytehattan