题目描述 Description
给出一张n*n(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。
输入描述 Input Description
第一行为n，m（表示有m个删除的格子）
第二行到m+1行为x,y，分别表示删除格子所在的位置
x为第x行
y为第y列
输出描述 Output Description
一个数，即最大覆盖格数
样例输入 Sample Input
8 0
样例输出 Sample Output
32
数据范围及提示 Data Size & Hint
经典问题
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<queue> #include<algorithm> #define maxn 105 #define __maxNodes 13145 using namespace std; // 顶点、边的编号均从 0 开始 // 邻接表储存 vector<int> G[__maxNodes]; /* G[i] 存储顶点 i 出发的边的编号 */ typedef vector<int>::iterator iterator_t; int num_nodes; int num_left; int num_right; int num_edges; int matching[__maxNodes]; /* 存储求解结果 */ int check[__maxNodes]; int n,m,rec[maxn][maxn],cnt; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; bool judge(int y,int x){ if(x < 1 || x > n || y < 1 || y > n || rec[y][x]) return false; else return true; } bool dfs(int u) { for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点 int v = *i; if (!check[v]) { // 要求不在交替路中 check[v] = true; // 放入交替路 if (matching[v] == -1 || dfs(matching[v])) { // 如果是未盖点，说明交替路为增广路，则交换路径，并返回成功 matching[v] = u; matching[u] = v; return true; } } } return false; // 不存在增广路，返回失败 } int hungarian() { int ans = 0; memset(matching, -1, sizeof(matching)); for (int u=0; u < num_left; ++u) { if (matching[u] == -1) { memset(check, 0, sizeof(check)); if (dfs(u)) ++ans; } } return ans; } int main(){ cin>>n>>m; int x,y; for(int i = 1;i <= m;i++){ scanf("%d%d",&y,&x); rec[y][x] = 1; } int cu,cv; for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ if(rec[i][j]) continue; for(int k = 0;k < 4;k++){ int ny = i + dy[k]; int nx = j + dx[k]; if(judge(ny,nx)){ cu = (i-1)*n+j-1; cv = (ny-1)*n+nx-1; G[cu].push_back(cv); } } } } num_left = n*n; cout<<hungarian(); return 0; }