zoj1654 Place the Robots 二分图最大匹配

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=654

将每一行的包含空地的区域编号

再将每一列的包含空地的区域编号

然后把每一个横向块看作二部图中顶点的集合x中的顶点

竖向块看作集合y中的顶点，若两个块有公共的空地，则将他们连边

然后就转化为二分图最大匹配问题

代码：

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define maxn 51

 int xn,yn;

 int x[maxn*maxn],y[maxn*maxn];

 int xs[maxn][maxn],ys[maxn][maxn];

 int m,n;

 int g[maxn*maxn][maxn*maxn];

 int vis[maxn*maxn];

 char map[maxn][maxn];

 int ans;

 bool path(int u)

 {

    for(int v=;v<=yn;v++)

   {

       if(g[u][v] && vis[v]==)

       {

        vis[v]=;

         if(y[v]== || path(y[v]))

        {

          x[u]=v;

          y[v]=u;

          return ;

        }

       }

   }

   return ;

 }void MaxMatch()

 {

   ans=;

   memset(x,,sizeof(x));

   memset(y,,sizeof(y));

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

     if(!x[i])

     {

       memset(vis,,sizeof(vis));

       if(path(i))

            ans++;

     }

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

 }

 int main()

 {

    int t;

   scanf("%d",&t);

   int iCase=;

   while(t--)

   {

      printf("Case :%d\n",++iCase);

      scanf("%d%d",&m,&n);

      memset(xs,,sizeof(xs));

      memset(ys,,sizeof(ys));

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

      scanf("%s",map[i]);

      int num=;

      bool flag;

      for(int i=;i<m;i++)//对水平方向的块进行编号

      {

          flag=;

          for(int j=;j<n;j++)

          {

            if(map[i][j]=='o')

               {

                  if(flag==) num++;

                  xs[i][j]=num; flag=;

               }

            else if(map[i][j]=='#') flag=;

          }

     }

     xn=num;

     num=;

     for(int j=;j<n;j++)//对垂直方向的块进行编号

       {

           flag=;

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

           {

             if(map[i][j]=='o')

             {

                 if(flag==) num++;

                 ys[i][j]=num;flag=;

             }

             else if(map[i][j]=='#') flag=;

           }

       }

      yn=num;

      memset(g,,sizeof(g));

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

      {

        for(int j=;j<n;j++)

        {

            if(xs[i][j]) g[xs[i][j]][ys[i][j]]=;

        }

      }

      MaxMatch();

   }

   return ;

 }