HDU 1507 Uncle Tom's Inherited Land(黑白棋盘最大匹配)

[cpp]
/*
题意：N*M的矩形，向其中填充1*2的小块矩形，黑色的部分不能填充，问最多可以填充多少块。

题解：黑白棋最大匹配
将棋盘中i+j为奇数的做A集合，偶数的做B集合，相邻的则建立联系。于是便转换成寻找最大匹配的问题
*/

#include <iostream>
#define re(i, n) for(int i = 0; i < n; ++ i)
using namespace std;

const int nMax = 105;
const int mMax = 10010;
int N, M, K;
int map[nMax][nMax];//存储图中的数据
int G[mMax][5];//G[k][]表示与k = i * M + j相连的可填充点，邻接表建立AB集合之间的联系
int link[mMax];
int useif[mMax];
int num;//最大匹配数
int V;// N * M ：总节点数

void buildGraph()//建图，对G进行处理
{
    memset(G, -1, sizeof(G));
    re(i, N) re(j, M)
    {
        int u = i * M + j;
        int v = 0;
        if(!map[i][j] && ((i + j) & 1) == 1)//此点可填充，并且i+j为奇数
        {
            //左
            if(j > 0 && !map[i][j - 1])
            {
                G[u][v ++] = u - 1;
            }
            //右
            if(j < M - 1 && !map[i][j + 1])
            {
                G[u][v ++] = u + 1;
            }
            //上
            if(i > 0 && !map[i - 1][j])
            {
                G[u][v ++] = u - M;
            }
            //下
            if(i < N - 1 && !map[i + 1][j])
            {
                G[u][v ++] = u + M;
            }
        }
    }
}

int dfs(int t)
{
    for(int i = 0; G[t][i] != -1; ++ i)
    {
        int u = G[t][i];
        if(!useif[u])//因为邻接表结构，所以t、u肯定有联系，无需在进行map[][]判断
        {
            useif[u] = 1; www.zzzyk.com
            if(link[u] == -1 || dfs(link[u]))
            {
                link[u] = t;
                return 1;
            }
        }
    }
    return 0;
}

int maxMatch()
{
    num = 0;
    memset(link, -1, sizeof(link));
    re(i, V)
    {
        memset(useif, 0, sizeof(useif));
        if(dfs(i))
            num ++;
    }
    return num;
}

int main()
{
    //freopen("f://data.in", "r", stdin);
    while(scanf("%d %d", &N, &M) != EOF)
    {
        if(!N && !M) break;
        scanf("%d", &K);
        memset(map, 0, sizeof(map));
        re(i, K)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            map[a - 1][b - 1] = 1;
        }
        V = N * M;
        buildGraph();
        maxMatch();
        printf("%d\n", num);
        re(i, V)
        {
            if(link[i] != -1)//因为最大匹配，所以不会有重复，查找一次，然后输出即可
            {
                int u = link[i];
                printf("(%d,%d)--(%d,%d)\n", u / M + 1, u % M + 1, i / M + 1, i % M + 1);
            }
        }
        printf("\n");
    }
    return 0;
}
作者：lhshaoren

补充：软件开发 , C++ ,