题解：CF1284G Seollal

· · 题解

随 CF 时随到了这题，没思路，看了题解，因为我不会拟阵，所以只能研究 @Wu_Ren 大手子的题解，但并没有看懂。后来研究了好几天，自己想出来一个很好的理解方式，来提一下给大家看看。

主要的思想是，找到一组匹配后，每次添加一个未匹配的白点，从类似 Hall 定理的代数表达式上面，逐渐从不合法转为合法。下面是正文：

左上角的黑点太特殊了，这里我们先把它抠掉。和题解的前几步一样，一个容易发现的必要条件是，对任意非空黑点集合 S，其相邻结点的集合 N(S) 大小要大于 |S|。

接下来我们要证明，这个条件也是充分的。不过只有证明还不够，因此接下来会有一个构造性的证明。

因为有 |N(S)|\geq |S|，所以我们可以用 Dinic 算法构造出一个包含所有黑点的匹配。但此时一定不能包含所有白点，否则此时取 A 为黑点的集合，在 A 不为空的时候，就有 |N(A)|=|A|，不满足之前的必要条件了。

这说明，存在一个未匹配的白点。任取这样一个点 x，考察加完 x 之后，哪些集合 S 从不合法变为合法了。

那么对于 x 的所有邻居 y（x 是白点则 y 是黑点），所有包含 y 的集合 S，因为凭空多出了一个 x，因此一定有 |N'(S)|=|N(S)+x|>|N(S)|\geq |S|。

而 y 本身还有一个匹配点 z=p_y，则可以继续增广路遍历下去，含 z 的集合，同理，也一定合法了。那么你可以写一个 dfs，并记录一个 v 数组，遇到没访问过的点 y 就继续 dfs 对应的 p_y。可以证明，每次加完点 x 之后，刚好会导致所有包含一个 v_i=1 的点 i 的集合 S 变为合法。如果还存在 v_i=0 的点，则取出所有这些点构成的集合，仍然不合法。

最后你就去看，是否还存在 v_i=0 的点，如果存在，则能构造出一个集合 S 使得 |N(S)|=|S|，从而无解。不存在的话，下面可以根据 dfs 过程给出一个平凡的解：

这样每个黑点刚好连了两条边，容易通过极端原理说明无环。因为边数还不够连通，所以随便再添加一些边使得形成一棵树就可以了，用并查集实现很容易。复杂度瓶颈在于匹配，Dinic 可以做到 O(nm\sqrt{nm})。

#include<bits/stdc++.h>
using namespace std;
struct MF{
    int n,S,T;
    int hd[100005],nxt[300005],c[300005],dy[300005],tot=1;
    int cur[100005],l[100005];
    void addedge(int u,int v,int w){
        nxt[++tot]=hd[u],hd[u]=tot;
        c[tot]=w,dy[tot]=v;
    }
    void adde(int u,int v,int w){
        addedge(u,v,w);addedge(v,u,0);
    }
    long long ans;
    void clear(){
        for(int i=1;i<=n;++i)hd[i]=0;
        for(int i=1;i<=tot;++i)nxt[i]=c[i]=dy[i]=0;
        tot=1;ans=0;
    }
    bool getc(){
        for(int i=1;i<=n;++i)l[i]=1e9,cur[i]=hd[i];
        l[S]=0;
        queue<int>q;
        q.emplace(S);
        while(q.size()){
            int x=q.front();
            q.pop();
            for(int i=hd[x];i;i=nxt[i]){
                if(!c[i])continue;
                int cu=dy[i];
                if(l[cu]>l[x]+1){
                    l[cu]=l[x]+1;
                    q.emplace(cu);
                }
            }
        }
        return l[T]<1e9;
    }
    int dinic(int x,int rl){
        if(x==T){
            ans+=rl;
            return rl;
        }
        int rr=rl;
        for(int i=cur[x];i;i=nxt[i]){
            cur[x]=i;
            if(!c[i])continue;
            int cu=dy[i];
            if(l[cu]!=l[x]+1)continue;
            int zz=dinic(cu,min(rr,c[i]));
            c[i]-=zz,c[i^1]+=zz;
            rr-=zz;
            if(!rr)break;
        }
        return rl-rr;
    }
    int liu(){
        while(getc())dinic(S,INT_MAX);
        return ans;
    }
}M;
char s[25][25],ans[45][45];
#define mk(x,y) (((x)-1)*m+(y))
int mb[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,pp[405],ok[405],fa[405];
vector<int>gg[405];
int findfather(int x){
    return x==fa[x]?x:fa[x]=findfather(fa[x]);
}
void jia(int x,int y){
    int fx=findfather(x),fy=findfather(y);
    if(fx!=fy){
        int a1=(x-1)/m+1,a2=(x-1)%m+1,b1=(y-1)/m+1,b2=(y-1)%m+1;
        ans[a1+b1-1][a2+b2-1]='O';fa[fx]=fy;
    }
}
void dfs(int x){
    for(auto cu:gg[x]){
        if(ok[cu]||pp[cu]==x)continue;
        jia(cu,x),ok[cu]=1,dfs(pp[cu]);
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=2*n-1;++i){
            for(int j=1;j<=2*m-1;++j)ans[i][j]=' ';
            ans[i][2*m]=0;
        }
        M.n=n*m+2,M.S=n*m+1,M.T=n*m+2;
        M.clear();
        int c1=0;
        for(int i=1;i<=n*m;++i)pp[i]=ok[i]=0,fa[i]=i,gg[i].clear();
        for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
            ans[2*i-1][2*j-1]=s[i][j];
            if(i+j>2&&s[i][j]=='O'){
                if((i+j)%2==0){
                    M.adde(M.S,mk(i,j),1),++c1;
                    for(int k=0;k<4;++k){
                        int dx=i+mb[k][0],dy=j+mb[k][1];
                        if(dx<1||dx>n||dy<1||dy>m)continue;
                        if(s[dx][dy]=='O'){
                            M.adde(mk(i,j),mk(dx,dy),1);
                            gg[mk(dx,dy)].emplace_back(mk(i,j));
                        }
                    }
                }else M.adde(mk(i,j),M.T,1);
            }
        }
        if(M.liu()!=c1){
            puts("NO");continue;
        }
        for(int i=M.hd[M.S];i;i=M.nxt[i]){
            int cu=M.dy[i];
            for(int j=M.hd[cu];j;j=M.nxt[j])if(!M.c[j]){
                pp[cu]=M.dy[j];pp[pp[cu]]=cu;jia(cu,pp[cu]);
            }
        }
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
            if((i+j)%2==0||s[i][j]!='O'||pp[mk(i,j)])continue;
            dfs(mk(i,j));
        }
        int fl=1;
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
            if((i+j)%2||s[i][j]!='O'||i+j==2)continue;
            if(!ok[mk(i,j)])fl=0;
        }
        if(!fl){
            puts("NO");continue;
        }
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
            if(s[i][j]!='O')continue;
            if(i<n&&s[i+1][j]=='O')jia(mk(i,j),mk(i+1,j));
            if(j<m&&s[i][j+1]=='O')jia(mk(i,j),mk(i,j+1));
        }
        puts("YES");
        for(int i=1;i<=2*n-1;++i)printf("%s\n",ans[i]+1);
    }
    return 0;
}