【Tyvj1035】棋盘覆盖

2014-03-25
竞赛题解 / 图论
TYVJ二分图匈牙利算法

描述 Description

给出一张 nn(n<=100) 的国际象棋棋盘，其中被删除了一些点，问可以使用多少 12 的多米诺骨牌进行掩盖。

输入格式 InputFormat

第一行为 n，m（表示有 m 个删除的格子）。

第二行到 m+1 行为 x,y，分别表示删除格子所在的位置。x 为第 x 行，y 为第 y 列。

输出格式 OutputFormat

一个数，即最大覆盖格数。

样例输入 SampleInput

98 18
39 11
10 43
52 21
91 5
69 32
8 57
2 65
31 72
39 34
70 52
3 60
36 89
77 15
70 78
22 2
53 31
94 65
52 24

样例输出 SampleOutput

4792

注释 Hint

经典的求二分图最大匹配问题，匈牙利算法。

Tyvj 1035

代码 Code

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define id(x,y) x*n+y
int a[20000][10],b[100000];
int mat[20000];
bool u[20000];
int i,j,t,n,m,l,r,k,z,y,x;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1}; 
void make()
{
    int i,j,t,tt,tx,ty;
    k=0;
    for (i=0;i<n;i++) for (j=0;j<n;j++) if ((i+j)%2==0 && b[id(i,j)])
    {
        for (t=0;t<4;t++) 
        {
            tx=i+dx[t];ty=j+dy[t];
            tt=id(tx,ty);
            if (tx>=0 && tx<n && ty>=0 && ty<n && b[tt])
            {
                a[id(i,j)][++a[id(i,j)][0]]=tt;
            }
        }
    }
}
bool path(int s)
{
    int i,j,t;
    for (i=1;i<=a[s][0];i++)
    {
        j=a[s][i];
        if (!u[j])
        {
            u[j]=true;
            if (mat[j]==-1 || path(mat[j]))
            {
                mat[j]=s;
                return true;
            }
        }
    }
    return false;
}
void hungary()
{
    z=0;
    for (i=0;i<n*n;i++)
    {
        memset(u,0,sizeof(u));
        if (b[i] && path(i))
        {
            z++;
        }
    }
    printf("%d\n",z);
}
int main()
{
    memset(a,0,sizeof(a));
    memset(b,true,sizeof(b));
    memset(mat,-1,sizeof(mat));
    scanf("%d%d",&n,&m);
    for (i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        x--;y--;
        b[id(x,y)]=false;
    }
    make();
    hungary();
    return 0;
}