本文主要是介绍二分图试炼之棋盘覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
输入
8 0第一行包含两个整数 N 和 t，其中 t 为禁止放置的格子的数量。
接下来t行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。
输出
32输出一个整数，表示结果。
数据范围
1≤N≤100, 0≤t≤100
思路：
每一个骨牌所遮住的两个棋盘方格的横纵坐标之和一定一个是奇数，一个是偶数。不可能出现两个都是奇数或两个都是偶数。
所以转化为二分图寻找最大匹配数的问题（匈牙利算法）。
代码实现：
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
#define N 110
int n;
bool graph[N][N],st[N][N];
pair<int,int> match[N][N];
//记录当前节点匹配的节点
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
bool findPath(int i,int j)
{//匈牙利算法for(int k=0;k<4;k++){int a=i+dx[k],b=j+dy[k];if(a<=n&&a>=1&&b<=n&&b>=1){if(st[a][b]||graph[a][b])continue;st[a][b]=true;//标记当前节点已被访问pair<int,int> t=match[a][b];//获取当前节点的匹配访问if(t.first==0||findPath(t.first,t.second)){//若匹配节点为空或可以找到增广路径match[a][b]={i,j};//更新匹配节点return true;}}}return false;
}int main()
{int t;cin>>n>>t;while(t--){int x,y;cin>>x>>y;graph[x][y]=true;}int res=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(graph[i][j])continue;else if((i+j)%2==1){//一块骨牌一定会覆盖一个奇数点和一个偶数点memset(st,0,sizeof st);if(findPath(i,j))res++;}}}cout<<res<<endl;return 0;
}
这篇关于二分图试炼之棋盘覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
