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();

struct Node{int a,b;}L[len+][len+],R[len+][len+];

int k,n,S,T,f[],ans,a,b,x,y,c;char ch[];

int P(int x,int y){if(x==||y==n)return S;if(y==||x==n)return T;return (x-)*(n-)+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-)*(n-)+;T=S+;

    for(int i=;i<=T;i++)f[i]=i;

    f[S]=T;//一开始就断了

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

    for(int j=;j<=n-;j++)

    {

        L[i][j].a=P(i-,j);

        L[i][j].b=P(i,j);

    }

    for(int j=;j<=n;j++)

    for(int i=;i<=n-;i++)

    {

        R[i][j].a=P(i,j);

        R[i][j].b=P(i,j-);

    }

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

    {

        scanf("%d %d %s",&a,&b,ch);

        if(!ans)x=a,y=b,c=(ch[]=='N');

        scanf("%d %d %s",&a,&b,ch);

        if(ans)x=a,y=b,c=(ch[]=='N');

        if(c)dele(L[x][y]);else dele(R[x][y]);

        if(!ans)printf("TAK\n");else printf("NIE\n");

    }

    return ;

}

秒客网