HDU 4619 Warm up 2 贪心或者二分图匹配

给同一张横着的牌的所在的格子编同一样的号，这些格子对应x集合，给同一张竖着的牌所在的格子编同一样的号，对应y集合，同一个格子上既有横着的牌又有竖着的牌，那么就建一条边，有冲突就要拿走一张，结果是总的牌数-最大二分图匹配数···

贴代码：

 #include <cstdio>

 #include <cstring>

 #define N 1100

 int nx,ny;

 int cx[N],cy[N];

 int g[N][N];

 bool vis[N];

 int map[N][N];

 bool path(int u)

 {

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

     {

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

         {

             vis[v] =;

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

             {

                 cx[u] = v;

                 cy[v] =u;

                 return true;

             }

         }

     }

     return false;

 }

 int maxMatch()

 {

     int ans =;

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

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

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

     {

         if(cx[i] == -)

         {

             memset(vis,,sizeof(vis));

             if(path(i))

                 ++ans;

         }

     }

     return ans;

 }

 int main()

 {

 //    freopen("in.c","r",stdin);

     while(scanf("%d%d",&nx,&ny),nx&&ny)

     {

         memset(map,-,sizeof(map));

         int x,y;

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

         {

             scanf("%d%d",&x,&y);

             map[x][y] =i;

             map[x+][y]= i;

         }

         memset(g,,sizeof(g));

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

         {

             scanf("%d%d",&x,&y);

             if(map[x][y] != - ) g[map[x][y]][i] =;

             if(map[x][y+] != -) g[map[x][y+]][i] =;

         }

         printf("%d\n",nx+ny-maxMatch());

     }

     return ;

 }