首页 > 代码库 > POJ 2446 Chessboard（二分图最大匹配）
POJ 2446 Chessboard（二分图最大匹配）
题意：
M*N的棋盘，规定其中有K个格子不能放任何东西。(即不能被覆盖)
每一张牌的形状都是1*2，问这个棋盘能否被牌完全覆盖（K个格子除外）
思路：
M、N很小，把每一个可以覆盖的格子都离散成一个个点，然后二分图最大匹配。
一个重要的问题**:可不可能存在建完的图是这样的情况：1-2,2-3,3-4,4-5,5-1？这种情况二分图最大匹配是5，但实际上答案是不对的。
证明：不可能存在这样的由奇个点构成的环图。我们按这种方法来看看能不能构造出这样一个棋盘。
假设有2k+1个个格（奇数），则第k+1个格一定有一个位置。并且一定与第k个格和第k+2个格相邻。
假设第k个格与第k+2个格的横坐标之差是x，纵坐标之差是y。则有x+y=2。（画个图）
接下来添加第k-1个格和第k+3个格，然后添加第k-2个格和第k+4个格，......一直到添加完最后一对，即第1个格和第2k+1个格，然后结束。
每添加一对格时，可以发现新的x+y的值要么是上一次的x+y的值-2，要么是不变，要么是+2。
而真实的情况是添加到最后一对，即第1个格和第2k+1个格，这两个格子是相邻的，也就是最后一次的x+y=1。而这是不可能的。
故不存在那种图。故直接二分图最大匹配是正确的。
代码：
int n,m,k;int board[35][35];vector<int> graph[1500];int cx[1500],cy[1500];bool bmask[1500];int cc;int findPath(int u){ int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(!bmask[v]){ bmask[v]=true; if(cy[v]==-1||findPath(cy[v])){ cy[v]=u; cx[u]=v; return 1; } } } return 0;}int MaxMatch(){ int ans=0; rep(i,1,cc) cx[i]=cy[i]=-1; rep(i,1,cc) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int main(){ while(scanf("%d%d%d",&m,&n,&k)!=EOF){ mem(board,0); rep(i,1,k){ int x,y; scanf("%d%d",&y,&x); board[x][y]=-1; } rep(i,1,m) rep(j,1,n){ if(board[i][j]==-1) continue; board[i][j]=++cc; } rep(i,1,cc) graph[i].clear(); rep(k,0,3) rep(i,1,m) rep(j,1,n){ if(board[i][j]==-1) continue; int ni=i+uu[k], nj=j+vv[k]; if(ni>0 && ni<=m && nj>0 && nj<=n && board[ni][nj]!=-1) graph[board[i][j]].push_back(board[ni][nj]); } int dd=MaxMatch(); if(dd==cc) puts("YES"); else puts("NO"); }}
POJ 2446 Chessboard（二分图最大匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。