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

传送门

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

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

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

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

——代码

1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 6 const int MAXN = 1001; 7 int n, m, cnt, t, tot, k1, k2; 8 int head[10001], to[10001], next[10001], belong[10001], map[MAXN][MAXN]; 9 int dx[4] = , 10 dy[4] = ; 11 bool b[MAXN][MAXN], vis[10001]; 12 13 inline void add(int x, int y) 14 19 20 inline int find(int u) 21 34 } 35 } 36 return 0; 37 } 38 39 int main() 40 53 for(i = 0; i < n; i++) 54 for(j = 0; j <= m; j++) 55 if(!b[i][j]) 56 if((i + j) % 2 == 1) map[i][j] = ++k1; 57 else map[i][j] = ++k2; 58 for(i = 0; i < n; i++) 59 for(j = 0; j < m; j++) 60 if(!b[i][j] && (i + j) % 2 == 1) 61 for(k = 0; k <= 3; k++) 62 68 for(i = 1; i <= k1; i++) 69 73 if(2 * tot + t == n * m) printf("YES\n"); 74 else printf("NO\n"); 75 } 76 return 0; 77 }
View Code

上一篇：分块来水题

下一篇：[TyvjP1050] 最长公共子序列（DP）

---

二分图 最大匹配 匈牙利算法