[POJ2446] Chessboard（二分图最大匹配-匈牙利算法）

传送门

把所有非障碍的相邻格子彼此连一条边，然后求二分图最大匹配，看 tot * 2 + k 是否等于 n * m 即可。

但是连边不能重复，比如 a 格子 和 b 格子 相邻，不能 a 连 b ，b 也连 a。

所以可以人为规定，横纵坐标相加为 奇数 的格子连横纵坐标相加为 偶数 的格子。

如果一个格子横纵坐标相加为奇数，那么它的上下左右四个格子横纵坐标相加必定为偶数。

——代码

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int MAXN = ;

 int n, m, cnt, t, tot, k1, k2;

 int head[], to[], next[], belong[], map[MAXN][MAXN];

 int dx[] = {, , -, },

     dy[] = {, , , -};

 bool b[MAXN][MAXN], vis[];

 inline void add(int x, int y)

 {

     to[cnt] = y;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 inline int find(int u)

 {

     int i, v;

     for(i = head[u]; i != -; i = next[i])

     {

         v = to[i];

         if(!vis[v])

         {

             vis[v] = ;

             if(!belong[v] || find(belong[v]))

             {

                 belong[v] = u;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     int i, j, k, x, y;

     while(~scanf("%d %d %d", &n, &m, &t))

     {

         k1 = k2 = ;

         memset(head, -, sizeof(head));

         memset(belong, , sizeof(belong));

         memset(b, , sizeof(b));

         for(i = ; i <= t; i++)

         {

             scanf("%d %d", &x, &y);

             b[y - ][x - ] = ;

         }

         for(i = ; i < n; i++)

             for(j = ; j <= m; j++)

             if(!b[i][j])

                 if((i + j) %  == ) map[i][j] = ++k1;

                 else map[i][j] = ++k2;

         for(i = ; i < n; i++)

             for(j = ; j < m; j++)

                 if(!b[i][j] && (i + j) %  == )

                 for(k = ; k <= ; k++)

                 {

                     x = i + dx[k];

                     y = j + dy[k];

                     if(x >=  && x < n && y >=  && y < m && !b[x][y])

                         add(map[i][j], map[x][y]);

                 }

         for(i = ; i <= k1; i++)

         {

             memset(vis, , sizeof(vis));

             if(find(i)) tot++;

         }

         if( * tot + t == n * m) printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }