学步园

题目请戳这里

题目大意：给一些1*2的多米诺骨牌，放到一个棋盘中，n个横着放，m个竖着放，同向的牌不会有交叉，现在要拿掉一些骨牌保证每个格子最多被一个骨牌占领，求剩下最多骨牌数量。

题目分析：裸的二分匹配，经典的染色模型。对格子黑白染色，每张多米诺骨牌必占一黑一白2个格子，从白格子向黑格子建边，跑一下匈牙利即可。

骨牌坐标范围0-100，所以棋盘102*102，黑白点最多5202个，边不超过2000条，匈牙利复杂度是O(m*n)，够了。

详情请见代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<string>
using namespace std;
const int N = 5203;
const int M = 40005;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const double PI = acos(-1.0);
typedef __int64 ll;
//#pragma comment(linker, "/STACK:1024000000,1024000000")

struct node
{
    int to,next;
}edge[M];
int num,n,m;
int head[N];
bool flag[N];
int cx[N],cy[N];
int nn,mm;
void build(int s,int e)
{
    edge[num].to = e;
    edge[num].next = head[s];
    head[s] = num++;
}

int path(int cur)
{
    int i;
    for(i = head[cur];i != -1;i = edge[i].next)
    {
        if(flag[edge[i].to] == false)
        {
            flag[edge[i].to] = true;
            if(cy[edge[i].to] == -1 || path(cy[edge[i].to]))
            {
                cy[edge[i].to] = cur;
                cx[cur] = edge[i].to;
                return 1;
            }
        }
    }
    return 0;
}

int maxmatch()
{
    memset(cx,-1,sizeof(cx));
    memset(cy,-1,sizeof(cy));
    int i,ret;
    for(ret = 0,i = 1;i <= 5202;i ++)
        if(cx[i] == -1)
        {
            memset(flag,false,sizeof(flag));
            ret += path(i);
        }
    return ret;
}

int main()
{
    int a,b;
    //freopen("1009.in","r",stdin);
    //freopen("data.out","w",stdout);
    while(scanf("%d%d",&nn,&mm),(nn + mm))
    {
        num = 0;
        memset(head,-1,sizeof(head));
        while(nn --)//横向牌
        {
            scanf("%d%d",&a,&b);
            if((a+b)&1)//起点是黑点
            {
                if(b&1)
                    build(b*51+1+(a>>1),b*51+1+(a>>1));
                else
                    build(b*51+1+((a+1)>>1),b*51+((a+1)>>1));
            }
            else
            {
                if(b&1)
                    build(b*51+((a+1)>>1),b*51+1+((a+1)>>1));
                else
                    build(b*51+1+(a>>1),b*51+1+(a>>1));
            }
        }
        while(mm --)
        {
            scanf("%d%d",&a,&b);
            if((a+b)&1)
            {
                if(b&1)
                    build(b*51+52+(a>>1),b*51+1+(a>>1));
                else
                    build(b*51+51+((a+1)>>1),b*51+((a+1)>>1));
            }
            else
            {
                if(b&1)
                    build(b*51+((a+1)>>1),b*51+51+((a+1)>>1));
                else
                    build(b*51+((a>>1)+1),b*51+1+51+((a>>1)));
            }
        }
        printf("%d\n",maxmatch());
    }
    return 0;
}
//15MS	332K