二分图匈牙利模板

题目描述

一个矩形可以划分成M*N个小正方形，其中有一些小正方形不能使用。一个多米诺骨牌占用两个相邻的小正方形。试问整个区域内最多可以不重叠地放多少个多米诺骨牌且不占用任何一个被标记为无法使用的小正方形。

输入

第一行有两个用空格隔开的正整数M和N（M<=50，N<=50）。
第二行有一个正整数K，表示共有K个小正方形不能使用。输入数据保证K<=M*N。
以下K行每行有两个用空格隔开的数X和Y，表示第X行的第Y个小正方形不能使用。

输出

输出最多能放多少个多米诺骨牌。

样例输入

样例输出

  1 #include <bits/stdc++.h>
  2  
  3 using namespace std;
  4 const int maxn = 55;
  5 const int maxm = 3000;
  6 int n,m,k;
  7 int vis[maxm],Left[maxm];
  8 int mark[maxn][maxn];
  9 bool ok[maxn][maxn];
 10 int id[maxn][maxn];
 11 vector<int> l[maxm];
 12 set<int>up;
 13 int getid (int xx,int yy)
 14 {
 15     return (xx-1)*m+yy;
 16 }
 17 bool check (int xx,int yy)
 18 {
 19     if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&ok[xx][yy])
 20         return true;
 21     else
 22         return false;
 23 }
 24 void add (int x,int y)
 25 {
 26     l[x].push_back(y);
 27     l[y].push_back(x);
 28 }
 29 int dfs (int x)
 30 {
 31     for (int i=0;i<l[x].size();++i){
 32         int it = l[x][i];
 33         if(Left[it]==-1){
 34             Left[it] = x;
 35             return 1;
 36         }
 37         if (vis[it]) continue;
 38         vis[it] = 1;
 39         if(dfs(Left[it])){
 40             Left[it] = x;
 41             return 1;
 42         }
 43     }
 44     return 0;
 45 }
 46  
 47 int main()
 48 {
 49     //freopen("de.txt","r",stdin);
 50     while (~scanf("%d%d",&n,&m)){
 51     memset(ok,true,sizeof ok);
 52     memset(Left,-1,sizeof Left);
 53     scanf("%d",&k);
 54     for (int i=0;i<k;++i){
 55         int xx,yy;
 56         scanf("%d%d",&xx,&yy);
 57         ok[xx][yy] = false;
 58     }
 59     for (int i=1;i<=n;++i){
 60         int j;
 61         if (i%2) j=1;
 62         else j=2;
 63         for (;j<=m;j+=2){
 64             if (check(i,j)){
 65                 //printf("%d %d
",i,j);
 66                 int id = getid(i,j);
 67                 if (check(i+1,j)){
 68                     int id2 = getid(i+1,j);
 69                     add(id,id2);
 70                 }
 71                 if (check(i,j+1)){
 72                     int id2 = getid(i,j+1);
 73                     add(id,id2);
 74                 }
 75                 if (check(i-1,j)){
 76                     int id2 = getid(i-1,j);
 77                     add(id,id2);
 78                 }
 79                 if (check(i,j-1)){
 80                     int id2 = getid(i,j-1);
 81                     add(id,id2);
 82                 }
 83             }
 84         }
 85     }
 86     int ans = 0;
 87     for (int i=1;i<=n;++i){
 88         int j;
 89         if (i%2) j=1;
 90         else j=2;
 91         for (;j<=m;j+=2){
 92             if (check(i,j)){
 93                 memset(vis,0,sizeof vis);
 94                 int id = getid(i,j);
 95                 ans += dfs(id);
 96             }
 97         }
 98     }
 99     printf("%d
",ans);
100     }
101     return 0;
102 }