题目描述 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
经典问题
分析：二分图匹配的经典问题，将原图进行二分图染色，黑色块与白色块相连，求出的最大匹配就是答案.因为是格子与格子连边，不能保证连完后是一个有向图，因此在匈牙利算法的时候要标记两次.
做这道题的时候因为粗心把int开成了bool,if后面直接跟了分号，气哭了QAQ.
#include#include #include #include #include using namespace std;typedef vector ::iterator iterator_t;int n, m, ans, pipei[10010];int dx[] = { 0, -1, 0, 1 }, dy[] = { -1, 0, 1, 0 };int flag[110][110],vis[10010];int tot = 1, to[110010], nextt[100010], head[100010];vector e[10010];void add(int x, int y){ to[tot] = y; nextt[tot] = head[x]; head[x] = tot++;}bool judge(int x, int y){ if (x < 1 || x > n || y < 1 || y > n || flag[x][y]) return false; return true;}bool dfs(int u){ for (int i = head[u]; i;i = nextt[i]) { int v = to[i]; if (!vis[v]) { vis[v] = 1; if ((pipei[v] == -1)|| dfs(pipei[v])) { pipei[v] = u; pipei[u] = v; return true; } } } return false;}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); flag[x][y] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (flag[i][j]) continue; for (int k = 0; k < 4; k++) { int nx = i + dx[k], ny = j + dy[k]; if (judge(nx,ny)) { int t1 = (i - 1) * n + j , t2 = (nx - 1) * n + ny; add(t1, t2); } } } } memset(pipei, -1, sizeof(pipei)); for (int i = 0; i < n * n; i++) { if (pipei[i] == -1) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ans++; } } printf("%d\n", ans); return 0;}