铺地板 | FFY's Blog

题意

NS 中学新建了一个 n × n 的正方形广场，现在需要你用 1 × 2 的地板砖去铺这个广场。由于各种原因，广场上有些地方不能铺地板（比如那里种了一棵树或者有一个井盖）。显然，地板也不能重叠放置. 现在你需要求出最少有多少个格子不能被地板铺上（包括不能铺地板的地方）。

• 看出二分图
• 然后 $AC$ ~(滑稽)~

只要看出是二分图模型就非常简单
建双向边得出的$ans$最大匹配的二倍
但因为一条边连接两个点所以直接输出$n^2-ans$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=70;
int n,head[maxn*maxn],num,p[maxn*maxn];
int cnt,t,map[maxn][maxn];
bool use[maxn*maxn];
int mx[4]={0,0,-1,1};
int my[4]={1,-1,0,0};
char str[maxn];
struct fy{int to,next;}q[maxn*maxn*10];
void add(int a,int b){q[++num]=(fy){b,head[a]};head[a]=num;}
bool find(int a)
{
    for(int i=head[a];i;i=q[i].next)
    {
        int b=q[i].to;
        if(!use[b])
        {
            use[b]=true;
            if(!p[b]||find(p[b]))
            {
                p[b]=a;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    freopen("floor.in","r",stdin);
    freopen("floor.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);memset(head,0,sizeof head);
        cnt=0;num=0;memset(map,0,sizeof map);
        memset(p,0,sizeof p);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str);
            for(int j=0;j<n;j++)
            if(str[j]=='.')map[i][j+1]=++cnt;
        }
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
        if(map[i][j])
        {
            int a=map[i][j];
            for(int k=0;k<4;k++)
            {
                int b=map[i+mx[k]][j+my[k]];
                if(b)add(a,b);
            }
        }
        int ans=0;
        for(int i=1;i<=cnt;i++)
        {
            memset(use,false,sizeof use);
            if(find(i))ans++;
        }
        printf("%d\n",n*n-ans);
    }
    return 0;
}