首页 > 代码库 > Bipartitegraph2446
Bipartitegraph2446
题意:m*n的棋盘,有几个点不能覆盖,用1*2(可转成2*1)的矩形覆盖,不重叠,问能否覆盖。
思路:将棋盘分成黑白的,然后黑与白进行二分匹配即可。
对于每个点,都可以与它周围四个方向的任意一点用覆盖物覆盖,因而变成完备匹配问题
二分图最大匹配就是完备匹配
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int m,n,k,a,b,l[1200],num,e,ans;int x[4]= {0,-1,0,1};int y[4]= {-1,0,1,0};bool h[1000][1000],p[1200][1200],v[1200];bool go(int i){ for(int j=0; j<=e; j++) { if(p[i][j]&&!v[j]) { v[j]=1; if(l[j]==-1||go(l[j])) { l[j]=i; return true; } } } return false;}int main(){ while(scanf("%d%d%d",&m,&n,&k)!=EOF) { memset(h,0,sizeof(h)); memset(p,0,sizeof(p)); memset(l,-1,sizeof(l)); num=m*n-k;//需要覆盖的总点数 for(int i=0; i<k; i++) { scanf("%d%d",&a,&b); h[b-1][a-1]=1; } if(num%2) { cout<<"NO"<<endl; continue; } for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { int u=i*n+j; if(((i%2==0&&j%2==0)||(i%2&&j%2))&&!h[i][j]) {//待匹配的点中要除去 不需要匹配的点h for(int g=0; g<4; g++) { int xx=i+x[g]; int yy=j+y[g]; if(xx>=0&&xx<m&&yy>=0&&yy<n&&!h[xx][yy]) { p[u][xx*n+yy]=1;//与四周非H点建立边 } } } } } e=m*n;//所有带匹配的点,包含H点,因为不知道哪些是H点哪些不是,所有需要全部遍历 ans=0; for(int i=0; i<=e; i++) { memset(v,0,sizeof(v)); if(go(i))ans++; } if(ans==num/2)cout<<"YES"<<endl;//匹配边等于匹配点的一半(左右集合点数一样),则为完备匹配 else cout<<"NO"<<endl; } return 0;}
Bipartitegraph2446
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。