首页 > 代码库 > 【bzoj4423】 AMPPZ2013—Bytehattan
【bzoj4423】 AMPPZ2013—Bytehattan
http://www.lydsy.com/JudgeOnline/problem.php?id=4423 (题目链接)
题意
给出一个N*N的格点图，m次操作，每次切断U,V之间的边，问切断之后，U,V是否还连通。
Solution
看到这个题目我就想起了以前写过的一道线段树维护连通性的题。嗯数据范围百万，3秒，nlogn的应该跑得过。那么，二维线段树？
不不不，我是来做平面图的，想想对偶图有没有什么好的性质。考虑每次砍掉平面图一条边就是使对偶图中的两个区域合成了一个区域，就相当于给对偶图中的两个点连了边。考虑什么时候U,V无法连通。那么肯定是两个点之间已经被空白区域完全隔开，也就是对偶图中的点连成了一个环。那么怎么维护呢？很显然，并查集吧。
代码
// bzoj4423#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=1500*1500+10;int fa[maxn],n,m;char ch[10],ech[10];int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]);}int main() { scanf("%d%d",&n,&m); int last=1,x,y,x1,y1,ex,ey; for (int i=1;i<=(n-1)*(n-1)+1;i++) fa[i]=i; while (m--) { scanf("%d%d%s",&x1,&y1,ch); if (!last) scanf("%d%d%s",&x1,&y1,ch); else scanf("%d%d%s",&ex,&ey,ech); if (ch[0]==‘E‘) { x=y1==1 ? (n-1)*(n-1)+1 : (x1-1)*(n-1)+y1-1; y=y1==n ? (n-1)*(n-1)+1 : (x1-1)*(n-1)+y1; } else { x=x1==1 ? (n-1)*(n-1)+1 : (x1-2)*(n-1)+y1; y=x1==n ? (n-1)*(n-1)+1 : (x1-1)*(n-1)+y1; } if (find(x)^find(y)) fa[fa[x]]=fa[y],last=1; else last=0; if (last) puts("TAK"); else puts("NIE"); } return 0;}
【bzoj4423】 AMPPZ2013—Bytehattan
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。