HDU 1507 1*2格子铺矩阵 二分匹配坐标点
题意：
给定n*m的矩阵
z个点
下面z个点坐标表示坏点（无法铺设）
问最多铺设几个1*2的方格，并输出这些方格的匹配边
思路：
用二分匹配，每一个匹配表示2个坐标相连
2个坐标相连就是这2个坐标组成一个1*2的方格
把 能组成方格的2个坐标 建边
注意2维坐标1维化 i*M+j M>100
lef[x] = v 这个数组记录 匹配边 输出x v 就是答案
#include <iostream>#include <stdio.h>#include <string.h>#include <set>#include <queue>#include <algorithm>#include <cstdlib>#include <vector>#include <math.h>#define N 111#define M 101using namespace std;int n,m;int map[N][N];int lef[N*N];//lef[v]表示Y集的点v 当前连接的点 bool T[N*N]; //T[u] 表示Y集 u 是否已连接x集vector<int>G[N*N]; //匹配边 G[X集].push_back(Y集) 注意G 初始化bool match(int x){ // x和Y集 匹配 返回x点是否匹配成功for(int i=0; i<G[x].size(); i++){int v = G[x][i];if(!T[v]){T[v] = true;if(lef[v] == -1 || match( lef[v] )){lef[v] = x;return true;}}}return false;}int solve(){memset(lef, -1, sizeof(lef));int ans = 0;for(int i = 1; i<= n; i++)//X集匹配，X集点标号从 1-pn 匹配边是G[左点].size() for(int j = 1; j<=m; j++){memset(T, 0, sizeof(T));if( match( i*M +j ) ) ans++;}return ans;}void pipei(int x1,int y1,int x2,int y2){if(map[x2][y2] || map[x1][y1]) return ;if(x1>n || x2>n || y1>m || y2>m)return ;G[ x1*M + y1 ] .push_back( x2*M + y2);}void Have_map(){int i,j;for(i=1;i<=n;i++)for(j=1;j<=m;j++)G[i*M+j].clear();for(i=1;i<=n;i++)for(j=1;j<=m;j++){pipei(i,j, i, j+1);pipei(i,j+1, i,j);pipei(i,j, i+1, j);pipei(i+1, j, i, j);}}int main(){int i, j, z;while(~scanf("%d %d", &n, &m), n||m){memset(map,0,sizeof(map));scanf("%d",&z);while(z--){scanf("%d %d",&i,&j);map[i][j] = 1;}Have_map();int ans = solve();printf("%d\n",ans/2);if(ans==0){printf("\n");continue;}for(i=1;i<=n;i++)for(j=1;j<=m;j++){int x = i*M+j;if( lef[x] != -1 && lef[ lef[x] ] != -1){printf("(%d,%d)--(%d,%d)\n",i,j,lef[x]/M, lef[x]%M);lef[x] = lef[ lef[x] ] = -1;}}printf("\n");}return 0;}/*4 4121 11 42 32 43 13 23 33 44 14 24 34 4ans:21,2 -- 1,32,1 -- 2,2*/