[AMPPZ 2013]Bytehattan

先把题目链接贴在这里喵~

http://main.edu.pl/en/archive/amppz/2013/baj

话说真是一道让我严重怀疑我的智商的好题目，

话说此题第一感觉。嗯？似乎离线做做就可以了喵？

诶呦我艹，这个和强制在线一样的感觉是怎么一回事啊！

然后我苦思良久，终于在我他喵的苦思冥想之下，发现了——

此题果然非我所能破~

但是看了题解后顿时表示这么多年书白读了TAT

首先原图是平面图，且仅有删边操作

我们维护原图G的对偶图G'的一个子图G''，这个子图的连通性对应了G中各个域(各个方块)的连通性

一开始没有边被删去， V''=V' ， E'=Ø ，说明各个域都不连通

然后每(在G中)删一条边，就在G''中加上对应的那条边

我们注意到现在只有加边的操作，可以用并查集维护所有域的连通性！

而且因为平面图的对偶图仍是平面图，平面图的子图仍是平面图

所以易得G''是平面图

【引理】

　　•平面图G''描述了平面图G删去若干条边后各域的连通性。

　　•则G''画到平面上后的每个域对应了G的一个新增的连通分量。

【推论】

　　•如果G中的一条边是G的桥，那么在G''中加入这条边的对应边将引入新的环。

　　•如果G中的一条边是G的桥，那么这条边的对应边的两端是联通的。

于是只要使用并查集维护各域的联通性，每次加边前询问两端是否联通就成功解决该题目了~

没看懂不要紧，其实我也不知道我在说什么，还是看图吧

1.现在有 9 个域，互相不练通

2.oh，我们删掉了一条边

3.然后 2 和 5 两个域就联通了

那么什么时候两个点不练通了呢？注意第 2 行第 3 个点

4.2 3 5 6域都是联通的

5.我们又要删去一条边，但是 2 3域已经联通了！这样就形成了一个环！

6.我们发现第 2 行第 3 个点和其他点都不连通了

其实脑补一下就知道，如果有两个点不连通，那么一个点的周围一定会有想围墙一样围起来的区域，而且该区域不存在连向外边的边

题目变一变就变成普及组水题了……

 #include <cstdio>

 const int size=;

 namespace IOspace

 {

     inline char getch()

     {

         register char ch;

         do ch=getchar(); while (ch!='E' && ch!='N');

         return ch;

     }

     inline int getint()

     {

         register int num=;

         register char ch;

         do ch=getchar(); while (ch<'' || ch>'');

         do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');

         return num;

     }

     inline void putint(bool num)

     {

         if (num==) printf("TAK\n");

         else printf("NIE\n");

     }

 }

 int n, k;

 inline void swap(int & x, int & y) {int t=x; x=y; y=t;}

 struct node

 {

     int x, y;

     inline node() {}

     inline node(int _x, int _y):x(_x), y(_y) {}

 };

 inline int f(int x, int y) {if (x== || x==n || y== || y==n) return ; return (x-)*(n-)+y;}

 inline node getedge();

 int r[size];

 inline void prepare() {for (int i=;i<n*n;i++) r[i]=i;}

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

 inline void merge(int x, int y) {x=find(x); y=find(y); r[x]=y;}

 int main()

 {

     bool ans;

     node T, N;

     n=IOspace::getint(), k=IOspace::getint();

     prepare();

     ans=;

     for (int i=;i<=k;i++)

     {

         T=getedge(); N=getedge();

         if (ans) T=N;

         ans=find(T.x)==find(T.y);

         IOspace::putint(ans);

         merge(T.x, T.y);

     }

     return ;

 }

 inline node getedge()

 {

     int x=IOspace::getint(), y=IOspace::getint();

     char c=IOspace::getch();

     if (c=='N') return node(f(x-, y), f(x, y));

     if (c=='E') return node(f(x, y-), f(x, y));

 }

本傻装B系列

巴特西

[AMPPZ 2013]Bytehattan

最新文章

热门文章