【bzoj4423】[AMPPZ2013]Bytehattan（平面图转对偶图+并查集）

　　题目传送门：bzoj4423

　　如果是普通的删边判连通性，我们可以很显然的想到把操作离线下来，倒着加边。然而，这题强制在线。

　　虽然如此，但是题目所给的图是个平面图。那么我们把它转成对偶图试试看？

　　在对偶图上，删边变成了加边（把边两边的网格连通起来）。并且，我们可以发现，如果在对偶图上加边时发现出现了一个环，那么就说明这个环中间的格点被完全同外面的格点切断了联系（包括刚才删去的边两侧的点）。

　　于是我们就只需在对偶图上用并查集维护对偶图的连通性即可。

　　代码：

#include<cstdio>

#define maxn 1510

using namespace std;

int fa[maxn*maxn];

int n,m,lastans;

inline int getid(int x,int y)

{

    if(x<||y<||x>=n||y>=n)return ;

    else return (x-)*n+y;

}

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

void work(int x,int y,char op)

{

    int f1,f2;

    if(op=='N')f1=find(getid(x-,y)),f2=find(getid(x,y));

    else f1=find(getid(x,y-)),f2=find(getid(x,y));

    if(f1==f2)printf("NIE\n"),lastans=;

    else fa[f1]=f2,printf("TAK\n"),lastans=;

}

int main()

{

    scanf("%d%d",&n,&m);

    lastans=;

    for(int i=;i<=n*n;i++)fa[i]=i;

    for(int i=;i<=m;i++){

        int x1,y1,x2,y2;

        char c1,c2;

        scanf("%d %d %c %d %d %c",&x1,&y1,&c1,&x2,&y2,&c2);

        if(lastans)work(x1,y1,c1);

        else work(x2,y2,c2);

    }

}

bzoj4423

巴特西

【bzoj4423】[AMPPZ2013]Bytehattan（平面图转对偶图+并查集）

最新文章

热门文章