[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;
}

本文链接：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关口主战场谁与争锋？_宋宸鸿的博客-程序员宅基地

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