自动搬运

查看原文

来自洛谷，原作者为

	Acerkaio 物以类聚，鸟以群分

搬运于2025-08-24 23:14:06，当前版本为作者最后更新于2025-08-08 18:05:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们先写一个 $O(2^{n^2})$ 的顺序填写的暴力搜索，发现跑的非常慢。

然后我们考虑使用可撤销并查集快速维护联通块数量，我们按秩合并将并查集复杂度看成 $O(1)$，这样判断合法就是 $O(1)$ 的。

然后我们剪枝，考虑发现你每填一个点那么联通块的数量至多减少一，这启发我们判断若联通块的数量大于剩下未填的点的数量加二就可以直接退出了（因为最后要求剩下两个连通块）。

实测最大点 2.83s。

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;++i)
#define drep(i,a,b) for(reg int i=a;i>=b;--i)
#define pb push_back
#define ins insert
#define il inline
#define rint reg int
using namespace std;
int n,k,res,sum,tot;
int fa[65],sz[65];
bitset<10>a[10],b[10],vis[10];
int dir[4][2]{{1,0},{-1,0},{0,1},{0,-1}};
int ltk=0;
il int find(rint x){
    if(fa[x]==x)return x;
    return find(fa[x]);
}
stack<tuple<int,int,int>>stk;
il bool merge(rint x,rint y){
    rint X=find(x),Y=find(y);
    if(X==Y)return 0;
    ltk--;
    if(sz[X]>sz[Y])swap(X,Y);
    fa[X]=Y;
    stk.push({X,Y,sz[Y]});
    sz[Y]+=sz[X];
    return 1;
}
il void poop(){
    // cerr<<stk.size()<<'\n';
    auto &[X,Y,SZ]=stk.top();
    stk.pop();++ltk;
    fa[X]=X,sz[Y]=SZ;
}
il int val(rint x,rint y){
    return (x-1)*n+y;
}
il bool check(){
    return (sum+ltk)==2;
}
il void dfs(rint x,rint y){
    if((sum+ltk)>(k-sum)+2)return ;
    if(sum==k){res+=check();return;}
    if(y>n)return;
    if(x>n){dfs(1,y+1);return;}
    if(a[x][y]){
        b[x][y]=1;
        rint cnt=0;
        if(y!=1&&a[x][y-1]&&b[x][y-1]){
            cnt+=merge(val(x,y),val(x,y-1));
        }
        if(x!=1&&a[x-1][y]&&b[x-1][y]){
            cnt+=merge(val(x,y),val(x-1,y));
        }
        sum++;
        dfs(x+1,y);
        rep(i,1,cnt)poop();
        sum--;
        b[x][y]=0;
    }
    dfs(x+1,y);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    rep(i,1,64)fa[i]=i,sz[i]=1;
    rint sudssm=0;
    rep(i,1,n)rep(j,1,n){char c;cin>>c;a[i][j]=(c=='.');sudssm+=a[i][j];}
    
    dfs(1,1);cout<<res<<'\n';
    return 0;
}