Uncle Tom's Inherited Land* HDU - 1507 最大匹配

//首先将池塘舍去，然后将所有 i+j 为偶数的点当作 x，
//将所有 i+j 为奇数的点当作 y，
//然后直接拿 (x,y) 寻找增广路，
//通过上下左右进行查找匹配，
//再通过 link[x1][y1]=(x2,y2) 来记录匹配点
#include<bits/stdc++.h>
#define LL long long
const int N=1000+5;
const int dx[]= {-1,1,0,0};
const int dy[]= {0,0,-1,1};
using namespace std;
int n,m;
bool st[N][N];
bool g[N][N];
struct Node {
    int x;
    int y;
} match[N][N]; //存储偶数点匹配奇数点的坐标
bool dfs(int x,int y) {//偶数点 
    for(int i=0; i<4; i++) { //向上下左右四个方向搜索
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]&&!st[nx][ny]) { //未访问的土地
            st[nx][ny]=true;
            if(match[nx][ny].x==-1||dfs(match[nx][ny].x,match[nx][ny].y)) { //匹配成功
                match[nx][ny].x=x;
                match[nx][ny].y=y;
                return true;//存在增广路
            }
        }
    }
    return false;//不存在增广路
}

int main() {
    while(scanf("%d%d",&n,&m)!=EOF&&(n+m)) 
    {
        memset(match,-1,sizeof(match));
        memset(g,true,sizeof(g));
        int k;
        scanf("%d",&k);
        while(k--) 
        {
            int x,y;
            scanf("%d%d",&x,&y);
            g[x][y]=false;//水池 
        }
        int res=0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(g[i][j])  //土地
                    if((i+j)%2==0) { //偶数点
                        memset(st,false,sizeof(st));
                        if(dfs(i,j))//寻找增广路
                            res++;
                    }
        printf("%d\n",res);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(g[i][j])
                    if((i+j)%2==1)//奇数点
                        if(match[i][j].x!=-1) {
                            printf("(%d,%d)",match[i][j].x,match[i][j].y);
                            printf("--");
                            printf("(%d,%d)",i,j);
                            printf("\n");
                        }
    }
    return 0;
}

Uncle Tom's Inherited Land* HDU - 1507 最大匹配

原文：https://www.cnblogs.com/QingyuYYYYY/p/12401231.html