hdu1507 最大匹配

题目大意：

　　在 n*m在矩阵中，有一些点被标记为黑色，问可以多少对相邻的没有重复的白色块。

思路：

　　看上去与二分匹配毫无关系。但是没有其他好的解法，转化为二分匹配是正解。二分匹配的条件是{X,Y|E}, X（Y）集合内的元素没有关系。这题可以把i+j为奇数归为X，偶数则归为Y。从头开始扫描，只要某点不是黑色的，那么可以试着向上下左右建边，不过也需要四个方向的点不是黑色才可以。由于n ,m <=100，所有点数有10000，所有用邻接矩阵存图会超内存。用邻接表存图就好了。邻接表的存图方式是建立一个动态数组，如果有边u->v,则将v存入u的数组。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int N=,INF=0x3f3f3f3f;

 int cx[N],cy[N],dx[N],dy[N],vis[][];

 bool bmask[N];

 int nx,ny,dis,ans;

 vector<int> bmap[N];

 bool searchpath()

 {

     queue<int> q;

     dis=INF;

     memset(dx,-,sizeof(dx));

     memset(dy,-,sizeof(dy));

     for(int i=;i<=nx;i++)

     {

         if(cx[i]==-){ q.push(i); dx[i]=; }

         while(!q.empty())

         {

             int u=q.front(); q.pop();

             if(dx[u]>dis) break;

             for(int i=;i<bmap[u].size();i++)

             {

                 int v=bmap[u][i];

                 if(dy[v]==-)

                 {

                     dy[v]= dx[u] + ;

                     if(cy[v]==-) dis=dy[v];

                     else

                     {

                         dx[cy[v]]= dy[v]+;

                         q.push(cy[v]);

                     }

                 }

             }

         }

     }

     return dis!=INF;

 }

 int findpath(int u)

 {

     for(int i=;i<bmap[u].size();i++)

     {

         int v=bmap[u][i];

         if(!bmask[v]&&dy[v]==dx[u]+)

         {

             bmask[v]=;

             if(cy[v]!=-&&dy[v]==dis) continue;

             if(cy[v]==-||findpath(cy[v]))

             {

                 cy[v]=u; cx[u]=v;

                 return ;

             }

         }

     }

     return ;

 }

 void maxmatch()

 {

     ans=;

     memset(cx,-,sizeof(cx));

     memset(cy,-,sizeof(cy));

     while(searchpath())

     {

         memset(bmask,,sizeof(bmask));

         for(int i=;i<=nx;i++)

             if(cx[i]==-) ans+=findpath(i);

     }

 }

 void init()

 {

     for(int i=;i<N;i++) bmap[i].clear();

     memset(vis,,sizeof(vis));

 }

 int main()

 {

     //freopen("test.txt","r",stdin);

     int n,m,t,i,j,k,a,b;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         if(!n) break;

         init();

         scanf("%d",&t);

         while(t--)

         {

             scanf("%d%d",&i,&j);

             vis[i][j]=;

         }

         for(i=;i<=n;i++)

         {

             for(j=;j<=m;j++)

             {

                 if(!vis[i][j]&&((i+j)%))

                 {

                     a=(i-)*m + j;

                     if(!vis[i][j-]&&j>) //左

                     {

                         b=a-;

                         bmap[a].push_back(b);

                     }

                     if(!vis[i][j+]&&j<m) //右

                     {

                         b=a+;

                         bmap[a].push_back(b);

                     }

                     if(!vis[i-][j]&&i>)   //上

                     {

                         b=a-m;

                         bmap[a].push_back(b);

                     }

                     if(!vis[i+][j]&&i<n)   //下

                     {

                         b=a+m;

                         bmap[a].push_back(b);

                     }

                 }

             }

         }

         nx=ny=n*m;

         maxmatch();

         printf("%d\n",ans);

         for(i=;i<=n*m;i++)

         {

             if(cx[i]==-) continue;

             a=i/m; b=i%m;

             if(!b) b=m; else a++;

             printf("(%d,%d)--",a,b);

             a=cx[i]/m; b=cx[i]%m;

             if(!b) b=m; else a++;

             printf("(%d,%d)\n",a,b);

         }

     }

     return ;

 }

巴特西

hdu1507 最大匹配

最新文章

热门文章