P10665 Bytehattan题解

· · 题解

对偶图+并查集

截止2024.8.15，我是本题最劣解。

这题第一眼看到时会发现是显然的连通性问题，因为每次只需要判断两个格点是否连通，我们考虑使用并查集。

那我太懂了，离线+时光倒流。这还评紫？ 和别的题目不同，本题要求强制在线。

那怎么办？开摆。 我们引入一种新图——对偶图。

什么是对偶图？我们可以简单理解：普通的图是以真点（我们称这种真实存在的点，也就是本题中的格点为真点）为点建图，而对偶图的独特在于，对偶图是以普通图中各个面（也就是普通的图中各个边所围成的面）为点来建图的。（可见下图，1,2,3,4,5 为原图的真点，x1,x2,x3,x4 为对偶图上由面转化而来的点）

注意上面的图中 x4 表示的是所有除 x1,x2,x3 之外的一整个大面。

接下来是关于对偶图的连边，我们将所有只有一条边相隔绝（也就是一条边的两边）的面构成的点建立虚边相连，也就是下面这张图。

仔细观察这张图，我们看看能发现什么和连通性有关的结论。

这里经过不懈的观察，我们会发现，在对偶图中成环的连边很有意思，拿环 x1,x2,x3,x4 来说，我们会发现，如果删去原图中与这些对偶图的边相应的真边，即 (1,2),(1,3),(3,4),(3,5) 或 (2,3),(1,3),(3,4),(3,5) 或将 (3,5) 用 (4,5) 替换。上述各组边如果被删去之后，原图也就变成了两个不连通的块。也就是说，对偶图上成环的边所对应的原图上的真边的真边集是原图的一个割。（这里的割就是网络流里面的割，但推广一下，也就是删去一个边集后原图若被分为两个不连通的图的话，这个边集被称为一个割）

这是一个很有用的性质，考虑把这种性质迁移到这个题目里来。发现这题的操作是只删不加，我们可以这样考虑：对于每次删边，我们将这条边在对偶图上所隔绝的两个面用并查集并起来（因为它们合成了一个面），当我们发现这条边所隔绝的两个面在删去这条边前就已经在同一集合里，那么说明，如果这条边再删去，对偶图中就会产生环，也就是说，在这次删边操作后，有一个割已经被删去了，因此原图被该割给划分成了两个块，故该边链接的两点也就不连通了。

接下来考虑这题如何把原图和对偶图建立关系，因为原图是一个 n\times n 的网格图，我们可以考虑对于每个格点，设定它所对应的面（也就是对偶图中的点）为右下的面。 那么我们会发现，所有的面的标号最大为 (n-1)\times (n-1)+1 我们可以按照这种方式建图。（见下图，为样例的图）

对于这个正方形，我们左上角标号为 (1,1) 右下角为 (3,3) 中间每个面对应的是它左上角的那个格点。

需要注意的是，存在一些格点所对的面都是同一个大面，也就是 5 号面，这些点我们会在输入的时候处理出来，具体可见代码。

最后，就是删边的过程，我们发现对于一个点 (a,b) ，记它所对应的边的编号为 id[a][b] 如果它要删去和 (a+1,b) 之间的竖向连边，那么也就是这条边对应的左右两个面会连通，也就是 id[a][b-1],id[a][b] 会连通，若删去的是横向连边推导方式一样，实在不理解可以画一个图看一下。

不难发现根据上述推导，我们需要处理的格点编号是从 (0,0) 开始到 (n,n) 的。这里我用的是覆盖的方法，先将所有格点的对应面记成最大的面的编号 tot ，然后再遍历 (1,1) 到 (n-1,n-1) 的格点赋值，具体可见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+99;
int n,tot,q;
int id[1511][1511];
int f[N],cnt;
int find(int x){return f[x]==x ? x:f[x]=find(f[x]);}
bool last=true;
signed main(){
    scanf("%d%d",&n,&q);
    tot=(n-1)*(n-1)+1;//所有的面最多为这么多 
    for(int i=1;i<=tot;i++) f[i]=i;
    for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) id[i][j]=tot;//先全部赋值为最大面tot 
    for(int i=1;i<n;i++) for(int j=1;j<n;j++) id[i][j]=++cnt;//对于存在在大正方形里面的各个小面，把这个面的编号给左上角的点。 
    while(q--){
        int x,y,xx,yy;
        char op1,op2;
        scanf("%d%d%c",&x,&y,&op1);
        scanf("%d%d%c",&xx,&yy,&op2);
        if(!last) x=xx,y=yy,op1=op2;
        if(op1=='E'){
            int fu=find(id[x][y-1]),fv=find(id[x][y]);
            if(fu==fv){
                printf("NIE\n");
                last=false;
                continue;
            }
            printf("TAK\n");
            last=true;
            f[fu]=fv;
        }
        else{
            int fu=find(id[x-1][y]),fv=find(id[x][y]);
            if(fu==fv){
                printf("NIE\n");
                last=false;
                continue;
            }
            printf("TAK\n");
            last=true;
            f[fu]=fv;
        }
    }
    return 0;
}