图论题还是在于建图
题意
给定一个长度为 \(n \times m\) 的网格图，有的地方是白方块，有的是黑方块，有的啥也没用。
给你如下四种 \(L\) 形方块，询问是否存在方法，让这些方块正好就是给出的图的形状。
$ L $ 形方块如下
思路
二分图
-
首先我们要想，为什么需要二分图：
若能拼成，那么就说明白块的数量，刚好是黑块数量的两倍，因为黑块和白块互相独立，所以我们就可以应用二分图的思想进行匹配。
-
再次，我们想怎么建图
如果只用一个黑点匹配，那么我们不可能向四个方向连边，这样我们就不能确保最后的形状是 $ L $ 形的。
怎么办呢？
把同一个黑块分裂成两个！但是为了确保是 $ L $ 形的，我们让一个黑点连上下，一个黑点连左右的白点。至此，整个题的思路就出来了：
-
首先统计白点和黑点的数量，给每个黑点和白点编号。统计完后，如果原图中白块数量不是黑块数量的两倍，说明怎么配肯定配不出来；
-
再循环一次，让黑点跟白点连边；
-
二分图匹配，如果匹配数等于白点数，说明成功。
代码实现
#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 同样的题，时限小了，过不去，只能跑网络流。