【二分图+最大匹配】北大 poj 2446 Chessboard
?
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL : http://poj.org/problem?id=2446Name : 2446 ChessboardDate : Tuesday, December 6, 2011Time Stage : half and one hourResult: 9631289panyanyany2446Accepted176K16MSC++Test Data :Review :具体的解释，可以看一看大牛的解题报告：飘过的小牛: http://blog.csdn.net/niushuai666/article/details/7031267小媛在努力~: http://blog.csdn.net/zxy_snow/article/details/6249446//----------------------------------------*/#include <stdio.h>#include <string.h>#define MAXSIZE33intn, m, k ;boolmap[MAXSIZE][MAXSIZE] ;struct {int x, y ;} link[MAXSIZE][MAXSIZE] ;boolcover[MAXSIZE][MAXSIZE], graph[MAXSIZE][MAXSIZE] ;intdir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1} ;bool find (int py, int px){int i, j ;int x, y ;for (i = 0 ; i < 4 ; ++i){y = py + dir[i][0] ;x = px + dir[i][1] ;if ((y >= 0 && y < m && x >= 0 && x < n) &&// 判断边界(cover[y][x] == false) && !((y+x) & 1) &&// 横纵坐标和 为偶数(map[y][x])){cover[y][x] = true ;if ((link[y][x].x == -1) || find (link[y][x].y, link[y][x].x)){link[y][x].y = py ;link[y][x].x = px ;return true ;}}}return false ;}int main (){int i, j ;int y, x ;int sum ;while (~scanf ("%d%d%d", &m, &n, &k)){memset (map, true, sizeof (map)) ;for (i = 0 ; i < k ; ++i){scanf ("%d%d", &x, &y) ;// 它的默认图坐标是从0开始数的，而实际输入的是从1开始数的……map[y-1][x-1] = 0 ;}// 若可用格子数为奇数，则必然不能放满if ((m * n - k) & 1){puts ("NO") ;continue ;}memset (link, -1, sizeof (link)) ;sum = 0 ;for (i = 0 ; i < m ; ++i)for (j = 0 ; j < n ; ++j){// 从 横纵坐标和 为奇数的格子开始找if (((i+j) & 1) && map[i][j]){memset (cover, 0, sizeof (cover)) ;sum += find (i, j) ;}}//printf ("%d\n", sum) ;if (n*m - sum*2 == k)puts ("YES") ;elseputs ("NO") ;}return 0 ;}??