专栏文章

题解：CF1284G Seollal

sstrapplE
CF1284G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minrl9fs
此快照首次捕获于
2025/12/02 07:12
3 个月前
此快照最后确认于
2025/12/02 07:12
3 个月前
查看原文
随 CF 时随到了这题，没思路，看了题解，因为我不会拟阵，所以只能研究 @Wu_Ren 大手子的题解，但并没有看懂。后来研究了好几天，自己想出来一个很好的理解方式，来提一下给大家看看。
主要的思想是，找到一组匹配后，每次添加一个未匹配的白点，从类似 Hall 定理的代数表达式上面，逐渐从不合法转为合法。下面是正文：
左上角的黑点太特殊了，这里我们先把它抠掉。和题解的前几步一样，一个容易发现的必要条件是，对任意非空黑点集合 SS，其相邻结点的集合 N(S)N(S) 大小要大于 ∣S∣|S|。
接下来我们要证明，这个条件也是充分的。不过只有证明还不够，因此接下来会有一个构造性的证明。
因为有 ∣N(S)∣≥∣S∣|N(S)|\geq |S|，所以我们可以用 Dinic 算法构造出一个包含所有黑点的匹配。但此时一定不能包含所有白点，否则此时取 AA 为黑点的集合，在 AA 不为空的时候，就有 ∣N(A)∣=∣A∣|N(A)|=|A|，不满足之前的必要条件了。
这说明，存在一个未匹配的白点。任取这样一个点 xx，考察加完 xx 之后，哪些集合 SS 从不合法变为合法了。
那么对于 xx 的所有邻居 yy（xx 是白点则 yy 是黑点），所有包含 yy 的集合 SS，因为凭空多出了一个 xx，因此一定有 ∣N′(S)∣=∣N(S)+x∣>∣N(S)∣≥∣S∣|N'(S)|=|N(S)+x|>|N(S)|\geq |S|。
而 yy 本身还有一个匹配点 z=pyz=p_y，则可以继续增广路遍历下去，含 zz 的集合，同理，也一定合法了。那么你可以写一个 dfs，并记录一个 vv 数组，遇到没访问过的点 yy 就继续 dfs 对应的 pyp_y。可以证明，每次加完点 xx 之后，刚好会导致所有包含一个 vi=1v_i=1 的点 ii 的集合 SS 变为合法。如果还存在 vi=0v_i=0 的点，则取出所有这些点构成的集合，仍然不合法。
最后你就去看，是否还存在 vi=0v_i=0 的点，如果存在，则能构造出一个集合 SS 使得 ∣N(S)∣=∣S∣|N(S)|=|S|，从而无解。不存在的话，下面可以根据 dfs 过程给出一个平凡的解：
  • 对所有黑点 yy，连接 yy 与 pyp_y。
  • 对所有黑点 yy，找到第一次使得 vy=1v_y=1 的点 xx，连接 yy 与 xx。
这样每个黑点刚好连了两条边，容易通过极端原理说明无环。因为边数还不够连通，所以随便再添加一些边使得形成一棵树就可以了，用并查集实现很容易。复杂度瓶颈在于匹配，Dinic 可以做到 O(nmnm)O(nm\sqrt{nm})。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...