[bzoj4423][AMPPZ2013]Bytehattan——对偶图+并查集_ylsoi的博客-程序员宅基地

技术标签: 对偶图  并查集  

题目大意:

给定一个网格图,每一次在网格图中间删除一条边,然后询问这条边的两个端点是否连通。

思路:

这是一个平面图,而平面图的判断点的连通与否可以看两个点在对偶图中,中间是否有一个环将它们分为了环外和环内,也就是两个点之间有割。
又因为这两个点是直接相连的,如果这两个点之间有割,那么它们两个直接向连的边是一定在割中的。
于是直接判断这条边割开的这两个区域是否在之前就连通就好了,用并查集维护。

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define y1 fuckyou
typedef long long ll;

using namespace std;

void File(){
     
	freopen("bzoj4423.in","r",stdin);
	freopen("bzoj4423.out","w",stdout);
}

template<typename T>void read(T &_){
     
	T __=0,mul=1; char ch=getchar();
	while(!isdigit(ch)){
     
		if(ch=='-')mul=-1;
		ch=getchar();
	}
	while(isdigit(ch))__=(__<<1)+(__<<3)+(ch^'0'),ch=getchar();
	_=__*mul;
}

const int maxn=1500+10;
int n,m,fa[maxn*maxn];

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

bool solve(int x,int y,char ty){
     
	if(ty=='N'){
     //(a,b) -> (a,b+1)
		int u= x==1 ? 0 : (x-2)*(n-1)+y;
		int v= x==n ? 0 : (x-1)*(n-1)+y;
		if(find(u)==find(v))return 1;
		return (fa[find(u)]=find(v),0);
	}
	else{
     //(a,b) -> (a+1,b)
		int u= y==1 ? 0 : (x-1)*(n-1)+y-1;
		int v= y==n ? 0 : (x-1)*(n-1)+y;
		if(find(u)==find(v))return 1;
		return (fa[find(u)]=find(v),0);
	}
}

int main(){
     
	File();
	read(n); read(m);
	REP(i,0,(n-1)*(n-1))fa[i]=i;
	int lasans=0;
	int x1,y1,x2,y2;
	char s[5],t[5];
	REP(i,1,m){
     
		read(x1); read(y1); scanf("%s",s);
		read(x2); read(y2); scanf("%s",t);
		if(!lasans)lasans=solve(x1,y1,s[0]);
		else lasans=solve(x2,y2,t[0]);
		printf("%s\n",lasans ? "NIE" : "TAK");
	}
	return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ylsoi/article/details/82852348

智能推荐

深入 Java 应用性能调优实践_yuhaibao324的博客-程序员宅基地

让 Java 应用运行更快:性能调优工具及实践本文从以下8个方面深入讲解 Java 应用性能优化1、Java 性能诊断工具2、Java 应用代码诊断3、Java GC 诊断4、Java 性能优化实践5、JVM 调优:GC 之痛6、应用层调优:嗅到代码的坏味道7、数据库层调优:死锁噩梦8、性能调优:总结与建议Java 应用性能优化是一个老生常谈的话题,典型的性...

Arcgis for Javascript API下类似于百度搜索A、B、C、D marker的实现方式_a18826265589的博客-程序员宅基地

多说无益,首先贴两张图让大家看看具体的效果:图1、百度地图搜索结果图2、Arcgis for JavaScript实现的效果看到了效果,是不是各位有点小鸡动,是不是也宠宠欲动,有木有?但是具体是怎么实现的呢?下面我来详细的给各位说说我的实现思路吧。第一,数据。其实搜索的对象从类型上来说,应该是点、线、面都支持的,但是在实际的操作过程中,不论是百...

研究音频编解码要看什么书_weixin_30627381的博客-程序员宅基地

前言。。。。。。最近总是有人问研究音频编解码要看什么书其实这是一个很难回答的问题,原因有很多。首先,做工程首先一个问题就是和课本学习不同,不是看书能解决的。其次,音频编解码技术在国内研究的人很少包括总体的音频技术国内相对国外都研究的不多。(从中国的潜艇噪声技术一直解决不好就能看出一二)。第三,音频编解码技术是一种应用,而一般的书籍都是理论基础。只看理论书籍和应用脱...

分布式核心设计原则_漫玥刚花的博客-程序员宅基地

目录1、软件架构设计的六大原则1. 单一职责原则(Single Responsibility Principle - SRP)2. 开放封闭原则(Open Closed Principle - OCP)3. 里氏替换原则(Liskov Substitution Principle - LSP)4. 最少知识原则(Least Knowledge Principle - LKP)...

批量处理csv格式转换成xls_weixin_30849403的博客-程序员宅基地

结合下面的代码学习相关模块及函数方法的使用#coding:utf-8#导入相应模块import csvimport xlwtimport sysimport osimport fnmatch#另存为文件名def ex_file(mycsvfile): csvfile = open(mycsvfile,"rb") #cs...

【宸鸿币谈】:8.14 比特币再次下跌冲破10500支撑,10000关口主战场谁与争锋?_宋宸鸿的博客-程序员宅基地

禅师牵驴云游,突然驴滑向悬崖,禅师紧抓驴尾,可驴拼命挣扎,禅师只好放开:让你得胜吧!禅师叹:不相信别人的结果好吗?机会对于不能利用它的人来说毫无用处!正如风只对于能利用它的人才是动力,投资市场心若没有归属,否则走到哪里都是流浪!高峰只对攀登它而不是仰望它的人来说才有真正意义。花盆里长不出苍松,鸟笼里飞不出雄鹰,格局决定了结局,态度决定了高度,我虽是你人生的插曲,但是我会用我仅有的双手为你弹出最动人...

随便推点

GIS开发环境全面升级10.1_R芮R的博客-程序员宅基地

最近,因为公司开发的需要,对开发环境进行全面的升级,在这其中也遇到了不少问题,在之后将陆续整理出来,以便以后查看。之前开发环境:VS2008,ArcGIS9.3,ArcEngine9.3,Oracle10g,ArcSDE9.3,DevExpress9.3.4,Windows7 32位系统新开发环境:VS2010,ArcGIS10.1,ArcEngine10.1,Oracle11gR2,Ar...

trivial writeup 实验吧_FrancisQiu的博客-程序员宅基地

trivial-writeup-实验吧题目An unlocked terminal is displaying the following:Encryption complete, ENC(???,T0pS3cre7key) = Bot kmws mikferuigmzf rmfrxrwqe abs perudsf! Nvm kda ut ab8bv_w4ue0_ab8v_DDUYou ...

为什么Controller层接收的是Service层接口,Service层注入的是实现类?_Rk..的博客-程序员宅基地_controller注入service接口还是实现类

这个也是在写项目的过程中,遇到的一个bug。 此时Controller层自动装配的是Service层的接口实现类而不是接口,就会报如下错误: 后来搜集了一些资料,了解到为什么要这样的原因. (1)注入的就是实现类,只不过拿接口来接收,接收的类型为接口,面向接口编程,那么为何要面向接口编程?这就涉及到使用接口做代理,因为通过@autowired的对象是通过接口的方式会使用jdk动态代理,jdk动态代理只能对实现接口的类生成代理,而不能针...

jquery weui 菜单栏tabbar显示不正常_ldl_csdn_ios的博客-程序员宅基地

1、官方链接:http://jqweui.com/components#tabbar 2、需要注意的问题:tabbar显示在顶部而不是在底部: 需要自己设置增加一个样式:body, html { height: 100%; -webkit-tap-highlight-color: transparent; }

【私有云 VS 公有云】燕麦企业云盘谈私有云基础架构的6大构成要素_chunziup85660的博客-程序员宅基地

越来越多的企业加入到使用云存储的队伍中来,一部分企业目前正在使用公有云服务,另外一部分企业已在使用或计划构建企业内部的私有云存储服务。因每个企业面临的环境和目标不同,进而要想找到一个通用的私有云基础架构是十分困难的。针对此种情况,燕麦企业云盘(OATOS企业网盘)推出了基于云盘的云端私有云解决...

python日期格式不能被excel识别_如何利用python的xlrd模块读取日期格式的Excel_weixin_39844426的博客-程序员宅基地

经常使用python操作Excel,就会遇到各种坑,比如,有时候你读取到的某一单元格的数据,你预想的结果本来应该是这样的,但是它却是这样的,真是很蛋疼。于是你会找各种解决办法,去解决这个问题!所以鄙人共找到了这么几种方法,仅供参考。 这些方法都会使用到这么一个包:xlrd,一般都是python自带的导包import datetimeimport xlrd方法一:自己拼接日期(个人不建议这么做)de...

推荐文章

热门文章

相关标签