hdu 1507 Uncle Tom's Inherited Land(二分图匹配的活用 c语言版)

题意:
给定一个n*m的矩阵,黑点代表无效点,两个相邻白点为一组
问最多能找到多少组
解题：
此题很容易想到2分匹配，将矩形建成二分图，列行和为奇的为左边，列行和为偶的为右边；
不过要注意的是不能用邻接矩阵形式的二分图。
参考 The_One1989的空间
#include<stdio.h>
#include<string.h>
#define N 10211
#define M 101
int G[M][M],g[N],len[N],map[N][5],vis[N],link[N],n,m,s;
int move[4][2]={-1,0,1,0,0,1,0,-1};
int can(int t)
{
   int i;
   for(i=0;i<len[t];i++)
   {
      int v=map[t][i];
      if(!vis[v])
      {
         vis[v]=1;
         if(link[v]==-1||can(link[v]))
         {
            link[v]=t;
            return 1;
         }
      }
   }
   return 0;
}
int getans()
{
   int i,ans=0;
   memset(link,-1,sizeof(link));
   for(i=0;i<len[0];i++)
   {
      memset(vis,0,sizeof(vis));
      if(can(g[i])) ans++;
   }
   return ans;
}
int main()
{
   while(scanf("%d%d",&n,&m),n||m)
   {
      scanf("%d",&s);
      int x,y,i,j,k,a,b,x1,y1;
      memset(G,0,sizeof(G));
      memset(len,0,sizeof(len));
      while(s--)
      {
         scanf("%d%d",&x,&y);
         G[x][y]=1;
      }
      for(i=1;i<=n;i++)
      {
         for(j=1;j<=m;j++)if(((i+j)%2)&&!G[i][j])
         {
            a=(i-1)*m+j;
            int flag=0;
            for(k=0;k<4;k++)
            {
               x=i+move[k][0];
               y=j+move[k][1]; 
               if(x>0&&x<=n&&y>0&&y<=m&&!G[x][y])
               {
                  flag=1;
                  b=(x-1)*m+y;
                  map[a][len[a]++]=b;
               }
            }
            if(flag)
            {
               g[len[0]++]=a;
            }
         }
      }
      printf("%d\n",getans());
      for(i=1;i<=n*m;i++)if(link[i]!=-1)
      {
         x=(i-1)/m+1;/*十进制与二维坐标的转换 谨记*/
         y=(i-1)%m+1;
         x1=(link[i]-1)/m+1;
         y1=(link[i]-1)%m+1;
         /*输出路径*/
         printf("(%d,%d)--(%d,%d)\n",x,y,x1,y1);
      }
      printf("\n");
   }
   return 0;
}