TheTilesDivOne

作者：翁文涛

关键词：转化模型，网络流

题目简述

现在有一个$n \times m$的网格图，网格图的每个格子都有颜色，要么是黑色要么是白色，对于第$i$行$j$列的格子，假如$i+j$是偶数，那么这个格子是黑色的，否则是白色的。现在有些格子上放了障碍物，剩下的格子是空的。你有足够多的L型瓷砖，每个恰好能覆盖3个格子，他们看起来是这样的： $$OO \\ O$$ 现在你需要把这些瓷砖放到网格图上，满足：

1. 每块瓷砖都可以旋转任意多次90度
2. 每块瓷砖必须恰好覆盖3个格子
3. 瓷砖之间不能有任何位置重叠
4. 瓷砖不能覆盖到有障碍的格子
5. 瓷砖的转折处必须放在一个黑色格子上

现在问你最多能放多少瓷砖？

数据范围

$1 \leq n,m \leq 47$

题解

直接这样做并不好做，我们不妨转化一下模型。我们给每个格子定义一个变量$level$，表示这个格子的等级。那么，假如一个格子$(i,j)$是黑色的，$level_{i,j} = 2$，否则，假如$j$为奇数，$level_{i,j}=1$，否则$level_{i,j}=3$。我们可以发现，每一块合法的瓷砖，必然恰好每种等级的格子均包含1个，并且转折处是等级2的格子，等级1和等级3的格子均和等级2的格子相邻。那么现在问题就变成：

每块瓷砖对应了一条等级1->等级2->等级3的路径，且瓷砖相互不能重叠，瓷砖不能覆盖到障碍，要找尽量多的瓷砖。

这个问题就非常经典了，我们可以用网络流来做。设源点为$S$，汇点为$T$。将每个格子拆成两个点，$in_{i,j}$和$out_{i,j}$，假如$(i,j)$上有障碍，不做处理，否则，连一条从$in_{i,j}$出发到$out_{i,j}$，流量为$1$的边。同时，假如$(i,j)$和$(x,y)$相邻，连一条从$out_{i,j}$出发到$in_{x,y}$，流量为$1$的边。另外，假如$level_{i,j}=1$，连一条从$S$出发，到$in_{i,j}$，流量为$1$的边，假如$level_{i,j}=3$，连一条从$out_{i,j}$出发，到$T$，流量为$1$的边。最后求一遍从$S$到$T$的最大流即可。