UVA1514 Piece it together 题解

图论题还是在于建图

题意

给定一个长度为 \(n \times m\) 的网格图，有的地方是白方块，有的是黑方块，有的啥也没用。

给你如下四种 \(L\) 形方块，询问是否存在方法，让这些方块正好就是给出的图的形状。

$ L $ 形方块如下

思路

二分图

• 首先我们要想，为什么需要二分图：

  若能拼成，那么就说明白块的数量，刚好是黑块数量的两倍，因为黑块和白块互相独立，所以我们就可以应用二分图的思想进行匹配。

• 再次，我们想怎么建图

  如果只用一个黑点匹配，那么我们不可能向四个方向连边，这样我们就不能确保最后的形状是 $ L $ 形的。

  怎么办呢？

  把同一个黑块分裂成两个！但是为了确保是 $ L $ 形的，我们让一个黑点连上下，一个黑点连左右的白点。至此，整个题的思路就出来了：

1. 首先统计白点和黑点的数量，给每个黑点和白点编号。统计完后，如果原图中白块数量不是黑块数量的两倍，说明怎么配肯定配不出来；

2. 再循环一次，让黑点跟白点连边；

3. 二分图匹配，如果匹配数等于白点数，说明成功。

代码实现

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define il inline
const int M = 2e5 + 5;
const int P = 1e4 + 5;
const int N = 5e2 + 5;
using namespace std;
int max(int x,int y) { return x > y ? x : y; }
int min(int x,int y) { return x < y ? x : y; }

struct node {
	int u,v,next;
} edge[M << 2]; int head[P],num_edge;
int match[P],vis[P],cnt[N][N],black,white;
int ans,n,m,e,u,v,T;
char mp[N][N];

il int read() 
{
	int f=0,s=0;
	char ch=getchar();
	for(; !isdigit(ch); ch=getchar()) f |= (ch=='-');
	for(; isdigit(ch); ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
	return f ? -s : s;
}

il void add(int from,int to) 
{
	edge[++num_edge].u = from;
	edge[num_edge].v = to;
	edge[num_edge].next = head[from];
	head[from] = num_edge;
}

il bool dfs(int u) 
{
	for(int i=head[u]; i; i=edge[i].next) 
	{
		int v = edge[i].v;
		if(vis[v]) continue;
		vis[v] = 1;
		if(!match[v] || dfs(match[v])) 
		{
			match[v] = u;
			return true;
		}
	}
	return false;/*匈牙利板子*/
}

int main() 
{
	T = read();
	while(T--) 
	{
		memset(head , 0 , sizeof head);
		memset(match , 0 , sizeof match);
		num_edge = 0 , black = 0 , white = 0 , ans = 0;
		n = read() , m = read();
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) 
			{
				cin >> mp[i][j];
				if(mp[i][j] == 'B') cnt[i][j] = ++black;/*给每个黑白点编号*/
				if(mp[i][j] == 'W') cnt[i][j] = ++white;
			}
		if(black == 0 && white == 0) { puts("YES");/*黑点白点都没有直接不放就行了*/ continue; }
		if(black*2 != white) { puts("NO");/*如果本身就不匹配，那么说明肯定不行*/ continue; }
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++)
				if(mp[i][j] == 'B') 
				{
					if(i > 1 && mp[i-1][j] == 'W') add(cnt[i][j],cnt[i-1][j]);/*一个黑点分成两个点*/
					if(i < n && mp[i+1][j] == 'W') add(cnt[i][j],cnt[i+1][j]);/*连上下*/
					if(j > 1 && mp[i][j-1] == 'W') add(cnt[i][j]+black,cnt[i][j-1]);/*分裂后的黑点连左右*/
					if(j < m && mp[i][j+1] == 'W') add(cnt[i][j]+black,cnt[i][j+1]);
				}/*二分图跑匹配*/
		black*=2;/*黑点的数量要乘以二*/
		for(int i=1; i<=black; i++) 
		{
			memset(vis , 0 , sizeof vis);
			if(dfs(i)) ans++;
			else break;
		}
		if(ans == white) puts("YES");/*能匹配完，说明可以*/
		else puts("NO");
	}
	return 0;
}

复杂度 $ O(TnE) $ 可以通过。

这题也可以跑 dinic 网络流，复杂度可以更优，用二分图匹配做另一个 SP9890 同样的题，时限小了，过不去，只能跑网络流。