BZOJ 4423: [AMPPZ2013]Bytehattan 并查集+平面图转对偶图

4423: [AMPPZ2013]Bytehattan

Time Limit: 3 Sec Memory Limit: 128 MB Submit: 277 Solved: 183 [Submit][Status][Discuss]

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

想法：将平面图转换为对偶图后，删除边L，如果L两边的格子已经连通，那说明他们不连通了，否则将这个两个格子连通。

不连通即将这个两点分割到不同集合，而对偶图中的一个环即分割两个集合。对于这道题只需要判断这条边接上是否形成环就行了。

Ps:特殊点S,T之间的边已经删了，所以一开始就是连通的。

#include<cstdio>
const int len(1500);
struct Node{int a,b;}L[len+10][len+10],R[len+10][len+10];
int k,n,S,T,f[2260000],ans,a,b,x,y,c;char ch[10];
int P(int x,int y){if(x==0||y==n)return S;if(y==0||x==n)return T;return (x-1)*(n-1)+y;}
int gf(int x)
{
    int v=x,o;while(v!=f[v])v=f[v];
    for(;x!=f[x];x=o)o=f[x],f[x]=v;
    return v;
}
void dele(Node x)
{
    int fa=gf(x.a),fb=gf(x.b);
    ans=(fa==fb);f[fa]=fb;
}
int main()
{
    scanf("%d%d",&n,&k);S=(n-1)*(n-1)+1;T=S+1;
    for(int i=1;i<=T;i++)f[i]=i;
    f[S]=T;//一开始就断了 
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n-1;j++)
    {
        L[i][j].a=P(i-1,j);
        L[i][j].b=P(i,j);
    }
    for(int j=1;j<=n;j++)
    for(int i=1;i<=n-1;i++)
    {
        R[i][j].a=P(i,j);
        R[i][j].b=P(i,j-1);
    }
    for(int i=1;i<=k;i++)
    {
        scanf("%d %d %s",&a,&b,ch);
        if(!ans)x=a,y=b,c=(ch[0]=='N');
        scanf("%d %d %s",&a,&b,ch);
        if(ans)x=a,y=b,c=(ch[0]=='N');
        if(c)dele(L[x][y]);else dele(R[x][y]);
        if(!ans)printf("TAK\n");else printf("NIE\n");
    }
    return 0;
}