U64949 棋盘覆盖 二分图匹配

　　

题目描述

给定一个 nn 行 nn 列的棋盘，有 mm 个格子禁止放置。求最多能不重叠地往棋盘上放多少块长度为 22 、宽度为 11 的骨牌。

输入输出格式

输入格式：

第一行为 n,mn,m ；

第二行到 t+1t+1 行，每行为 x,yx,y ，表示禁止放置的格子所在的坐标为第 xx 行第 yy 列（行列坐标从 11 开始）。

输出格式：

一个数，即最多能放的骨牌数。

输入输出样例

输入样例#1： 复制

8 0

输出样例#1： 复制

32

跑匈牙利算法即可   
注意用时间戳优化的时候  一开始flag不能为0  因为初始化都是0

二分图匹配模型的两个要素

1. 节点能分成两个集合，每个集合内部有 00 条边。简称 00 要素。
2. 每个节点只能与 11 条匹配边相连。简称 11 要素。

两个要素在本题中的体现

11 要素：每个格子只能被一张骨牌覆盖，一张骨牌覆盖 22 个相邻的格子。

把棋盘上没有被禁止的格子作为节点，骨牌作为边（两个相邻的格子对应的节点之间连边）。

00 要素：把棋盘黑白相间染色，相同颜色的格子不可能被同一骨牌覆盖。

那么，若把白色格子作为左部节点，黑色格子作为右部节点，则刚才建立的无向图是二分图。

使用匈牙利算法求上述二分图的最大匹配，时间复杂度为 O(n^2m^2)O(n2m2) 。

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=1000000+5;
const int M=2000000+5;
int head[M],pos,n,m,flag;
struct Edge
{
    int nex,to;
}edge[M];
void add(int a,int b)
{
    edge[++pos].nex=head[a];
    head[a]=pos;
    edge[pos].to=b;
}
int vis[N],used[N];
bool dfs(int x)
{
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(flag!=used[v])
        {
            used[v]=flag;
            if(!vis[v]||dfs(vis[v]))
            {
                vis[v]=x;
                return true;
            }
        }
    }
    return false;
}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int mp[200][200];
int id(int x,int y){return (x)*n+y;}
int main()
{
    RII(n,m);
    while(m--)
    {
        int a,b;RII(a,b);mp[a][b]=1;
    }
    rep(i,1,n)
    rep(j,1,n)
    if(!mp[i][j])
    {
        if((i+j)%2)
        {
            rep(k,0,3)
            {
                int x=i+dx[k],y=j+dy[k];
                if(x<=n&&x>=1&&y>=1&&y<=n&&!mp[x][y])
                    add(id(i,j),id(x,y));
            }
        }
    }
    int ans=0;
    rep(i,1,n)
    rep(j,1,n)
    if((i+j)%2)
    flag++,ans+=dfs(id(i,j));

    cout<<ans;
}