首页 > 代码库 > [POJ2446] Chessboard（二分图最大匹配-匈牙利算法）
[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] = {0, 1, -1, 0},10 dy[4] = {1, 0, 0, -1};11 bool b[MAXN][MAXN], vis[10001];12 13 inline void add(int x, int y)14 {15 to[cnt] = y;16 next[cnt] = head[x];17 head[x] = cnt++;18 }19 20 inline int find(int u)21 {22 int i, v;23 for(i = head[u]; i != -1; i = next[i])24 {25 v = to[i];26 if(!vis[v])27 {28 vis[v] = 1;29 if(!belong[v] || find(belong[v]))30 {31 belong[v] = u;32 return 1;33 }34 }35 }36 return 0;37 }38 39 int main()40 {41 int i, j, k, x, y;42 while(~scanf("%d %d %d", &n, &m, &t))43 {44 k1 = k2 = 0;45 memset(head, -1, sizeof(head));46 memset(belong, 0, sizeof(belong));47 memset(b, 0, sizeof(b));48 for(i = 1; i <= t; i++)49 {50 scanf("%d %d", &x, &y);51 b[y - 1][x - 1] = 1;52 }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 {63 x = i + dx[k];64 y = j + dy[k];65 if(x >= 0 && x < n && y >= 0 && y < m && !b[x][y])66 add(map[i][j], map[x][y]);67 }68 for(i = 1; i <= k1; i++)69 {70 memset(vis, 0, sizeof(vis));71 if(find(i)) tot++;72 }73 if(2 * tot + t == n * m) printf("YES\n");74 else printf("NO\n");75 }76 return 0;77 }
[POJ2446] Chessboard（二分图最大匹配-匈牙利算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。