首页 > 代码库 > 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