1302: 棋盘覆盖(二分图）

解题思路:

问题转化：

    将棋盘覆盖转化为二分图匹配多米诺骨牌需覆盖相邻两格，且必然是一个黑格和一个白格（类似国际象棋棋盘染色）

    因此问题等价于：在剩余格子中，最多能找到多少对相邻的黑 - 白格组合；

二分图构建：

    以黑格（(i+j) 为偶数的格子）作为二分图左集合，白格（(i+j) 为奇数的格子）作为右集合

    对每个未被移除的黑格，向其上下左右四个方向的未被移除白格建立边（表示可被同一骨牌覆盖）

最大匹配求解 - 使用匈牙利算法寻找二分图的最大匹配：

    对每个黑格尝试通过 DFS 寻找增广路径（交替经过未匹配边和已匹配边的路径）

    找到增广路径后翻转路径上的边状态，使匹配数增加 1

    重复直至无法找到新的增广路径，此时匹配数达到最大

结果映射

    二分图的最大匹配数即为最多能放置的多米诺骨牌数量（每个匹配对应一个骨牌）

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;  // 棋盘最大尺寸为100x100，定义数组大小
int g[N][N];             // 标记棋盘格子状态，-1表示被移除的格子
int n, m;                // n是棋盘大小，m是被移除的格子数量
// 方向数组，用于遍历上下左右四个相邻格子
int d[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int mx;                  // 存储最大匹配数
int match[N*N];          // 匹配数组，match[v]表示与v匹配的u节点
bool v[N * N];           // 标记数组，用于DFS中避免重复访问
vector<int> adj[N*N];    // 邻接表，存储二分图的边
// 将二维坐标(x,y)转换为一维唯一标识符
int get_id(int x, int y){
    return (x - 1) * n + y;  // 计算方式确保每个格子有唯一ID
}
// 匈牙利算法核心：深度优先搜索寻找增广路径
bool dfs(int u){
    // 遍历u的所有邻接节点v
    for(auto t : adj[u]){
        if(!v[t]){          // 如果v未被访问过
            v[t] = true;    // 标记为已访问
            
            // 若v未匹配，或v的匹配节点可以找到其他匹配
            if (match[t] == 0 || dfs(match[t])){
                match[t] = u;  // 将v匹配给u
                return true;   // 找到增广路径，返回成功
            }
        }
    }
    return false;  // 未找到增广路径，返回失败
}
int main()
{
    cin >> n >> m;  // 输入棋盘大小和被移除的格子数量
    
    // 标记被移除的格子
    for(int i = 1; i <= m; ++ i){
        int x, y;
        cin >> x >> y;
        g[x][y] = -1;  // 用-1标记该格子已被移除
    }
    
    // 构建二分图：只处理黑格((i+j)为偶数)，并连接相邻的白格
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            // 只处理未被移除的黑格
            if((i + j) % 2 == 0 && g[i][j] != -1){
                // 遍历四个方向的相邻格子
                for(int k = 0; k < 4; ++ k){
                    int nx = i + d[k][0];  // 新行坐标
                    int ny = j + d[k][1];  // 新列坐标
                    
                    // 检查相邻格子是否在棋盘范围内且未被移除
                    if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && g[nx][ny] != -1)
                        // 向邻接表添加边：当前黑格 -> 相邻白格
                        adj[get_id(i,j)].push_back(get_id(nx, ny));
                }
            }
        }
    }
    
    // 计算二分图的最大匹配
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            // 对每个未被移除的黑格尝试寻找匹配
            if((i + j) % 2 == 0 && g[i][j] != -1){
                memset(v, 0, sizeof v);  // 重置访问标记
                if(dfs(get_id(i,j)))     // 找到增广路径，匹配数+1
                    mx += 1;
            }
        }
    }
    
    // 最大匹配数即为最多能放置的多米诺骨牌数量
    cout << mx;
    return 0;
}