poj 2446 Chessboard(二分匹配)

解题思路

题意：

       玩个游戏：给出一个m行n列的棋盘，里面有m*n个方格，其中有k个格子上有洞，我们称那些没洞的格子叫正常的格子（normal grid）,Bob要遵循两个规则去玩： （1）任何一个正常的格子都要被一张卡覆盖，（卡片是1*2规格的） （2）一张卡要正好覆盖两个相邻的正常格子

我们的任务是帮助Bob决定是否棋盘在上述两个规则下能被覆盖。

 

思路：

因为棋盘上都是两个格子放一张卡片，所以到最后肯定是两个点两个点连着的。由此想到了二分匹配，具体是这样的：

 

 

给每个格子编号，从第一行到最后一行编号为1—12 ，然后每个点跟临近的正常点连接，这就建成了二分图，如右上图。

然后以此建邻接表，建表时，枚举每个点，如果是正常点i，那么与他相邻的正常点(v)的邻接点数增一（g[v][0]++），并使g[v][g[v][0]] = i;

然后就是二分匹配模版了，完后看匹配数是否等于正常格子数，即是否能构成完美匹配。

源程序

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 34
#define M N*N

int g[M][5], used[M], mat[M];
int match, m, n;

int find(int k)
{
    int i, j;

    for(i=1; i<=g[k][0]; i++)
    {
        j = g[k][i];
        if(!used[j])
        {
            used[j] = 1;
            if(!mat[j] || find(mat[j]))
            {
                mat[j] = k;
                return 1;
            }
        }
    }
    return 0;
}

void hungary()
{
    int i;
    for(i=1; i<=m*n; i++)
    {
        if(g[i][0] != -1 && g[i][0] != 0)
        {
            match += find(i);
            memset(used, 0, sizeof(used));
        }
    }
}

int main()
{
    int i, j;
    int k;
    int x, y;
    freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &m, &n, &k);

    for(i=1; i<=k; i++)
    {
        scanf("%d%d", &x, &y);
        g[x+(y-1)*n][0] = -1;
    }
    for(i=1; i<=m*n; i++)
    {
        if(g[i][0] != -1)
        {
            //left

            if((i-1)%n >= 1 && g[i-1][0] != -1)
                g[i-1][++g[i-1][0]] = i;
            //right

            if(i%n != 0 && g[i+1][0] != -1)
                g[i+1][++g[i+1][0]] = i;
            //up

            if((i-(i%n)) / n >= 1 && g[i-n][0] != -1)
                g[i-n][++g[i-n][0]] = i;
            //down

            if((i-(i%n)+1) / n <= m && g[i+n][0] != -1)
                g[i+n][++g[i+n][0]] = i;
        }
    }
    match = 0;
    hungary();
    
    if(match == m*n-k)
        printf("YES\n");
    else printf("NO\n");
    //printf("%d\n", match);

    getch();
    return 0;
}

Problem:		User:
Memory: 192K		Time: 0MS
Language: C++		Result: Accepted