二分图的最大匹配

考虑一个格子(i,j)(i,j):

i+j为偶数:不妨记这样的格子为白格子.
i+j为奇数:不妨记这样的格子为黑格子.
如果这个白格子没有被禁止,那么就让它向周围没有被禁止的黑格子连有向边,表示 如果选择这条边(在这两个格子上放骨牌)会对答案有1的贡献.显然白格子周围都是黑格子,所以白格子之间不会有边.那么这就是一个二分图最大匹配的模型,跑一下就好了.

题目描述

给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数 N 和 t，其中 t 为禁止放置的格子的数量。

接下来 t 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。

输出格式

输出一个整数，表示结果。

数据范围

1≤N≤100,
0≤t≤100

样例

输入样例：

8 0

输出样例：

32

匈牙利算法

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first 
#define y second

using namespace std;

typedef pair<int , int>PII;

const int N = 110;

int n , m;
PII match[N][N];
bool g[N][N] , st[N][N];

bool find(int x , int y)
{
    int dx[] = {-1 , 0 , 1 , 0} , dy[] = {0 , 1 , 0 , -1};

    for(int i = 0 ; i < 4 ; i ++ )
    {
        int a = x + dx[i] , b = y + dy[i];
        if(a < 1 || a > n || b < 1 || b > n) continue;
        if(st[a][b] || g[a][b]) continue;

        st[a][b] = true;
        PII t = match[a][b];
        if(t.x == 0 || find(t.x , t.y)) 
        {
            match[a][b] = {x , y};
            return true;
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;
    while(m -- )
    {
        int x , y;
        cin >> x >> y;
        g[x][y] = true;//禁止放置
    }

    int res = 0;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
            if((i + j) % 2 && !g[i][j])//枚举奇数
            {
                memset(st , 0  ,sizeof st);
                if(find(i , j)) res ++ ;
            }

    cout << res << endl;

    return 0;
}