二分图匹配，每个点只判断与其周围各点的匹配情况，难点在于对于一个编号求期所在的行列，以及对于给出的坐标求编号。
View Code #include < iostream > #include < cstdio > #include < cstdlib > #include < cstring > using namespace std; #define maxn 70 int n, m, h; bool map[maxn][maxn]; int xM[maxn * maxn], yM[maxn * maxn]; bool chk[maxn * maxn]; int uN, vN; int dir[ 4 ][ 2 ] = { { 1 , 0 },{ 0 , 1 },{ - 1 , 0 },{ 0 , - 1 } }; int getx( int a){ if (m & 1 ) return (a * 2 + 1 ) / m; return a / (m / 2 );} int gety( int a){ if (m & 1 ) return (a * 2 + 1 ) % m; int x = getx(a); return 1 - x % 2 + (a * 2 - x * m);} int hash( int x, int y){ if (x < 0 || y < 0 || x >= n || y >= m) return - 1 ; if (map[x][y]) return - 1 ; if (m & 1 ) return (x * m + y) / 2 ; return x * (m / 2 ) + y / 2 ;} bool SearchPath( int u){ int x = getx(u); int y = gety(u); if (map[x][y]) return false ; for ( int i = 0 ; i < 4 ; i ++ ) { int v = hash(x + dir[i][ 0 ], y + dir[i][ 1 ]); if (v != - 1 && ! chk[v]) { chk[v] = true ; if (yM[v] == - 1 || SearchPath(yM[v])) { yM[v] = u; xM[u] = v; return true ; } } } return false ;} int MaxMatch(){ int u, ret = 0 ; memset(xM, - 1 , sizeof (xM)); memset(yM, - 1 , sizeof (yM)); for (u = 0 ; u < uN; u ++ ) if (xM[u] == - 1 ) { memset(chk, 0 , sizeof (chk)); if (SearchPath(u)) ret ++ ; } return ret;} int main(){ // freopen("t.txt", "r", stdin); scanf( " %d%d%d " , & n, & m, & h); memset(map, 0 , sizeof (map)); uN = m * n / 2 ; vN = m * n - uN; for ( int i = 0 ; i < h; i ++ ) { int a, b; scanf( " %d%d " , & a, & b); a -- ; b -- ; map[b][a] = true ; } if ((m * n - h) & 1 ) { printf( " NO\n " ); return 0 ; } int ans = MaxMatch(); if (ans < (m * n - h) / 2 ) printf( " NO\n " ); else printf( " YES\n " ); return 0 ;}