思路：把所有涉及到的点按（x+y）的奇偶分成两部分点，对所有的1*2的骨牌，都有(x+y)为偶数的建到奇数的边。求一次最大匹配，就是答案。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #define Maxn 2010 using namespace std; int match[Maxn],map[Maxn][Maxn],vi[Maxn],ny,nx,graphic[Maxn][Maxn]; struct Point{ int x, y; }hori[Maxn],vert[Maxn]; void init() { memset(map,0,sizeof(map)); memset(graphic,0,sizeof(graphic)); nx=ny=0; } int dfs(int u) { int i,j; for(i=1;i<=ny;i++) { if(!vi[i]&&graphic[u][i]) { vi[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } } return 0; } int main() { int n,m,i,j,x,y; while(scanf("%d%d",&n,&m),n||m) { init(); int mx,my; mx=my=0; for(i=1;i<=n;i++) { scanf("%d%d",&hori[i].x,&hori[i].y); map[hori[i].x][hori[i].y]=1; map[hori[i].x+1][hori[i].y]=1; mx=max(mx,hori[i].x+1); my=max(my,hori[i].y); } for(i=1;i<=m;i++) { scanf("%d%d",&vert[i].x,&vert[i].y); map[vert[i].x][vert[i].y]=1; map[vert[i].x][vert[i].y+1]=1; mx=max(mx,vert[i].x); my=max(my,vert[i].y+1); } nx=ny=0; for(i=0;i<=mx;i++) for(j=0;j<=my;j++) { if(map[i][j]) { if((i+j)%2==0) map[i][j]=++nx; else map[i][j]=++ny; } } for(i=1;i<=n;i++) { x=map[hori[i].x][hori[i].y]; y=map[hori[i].x+1][hori[i].y]; if((hori[i].x+hori[i].y)%2==0) graphic[x][y]=1; else graphic[y][x]=1; } for(i=1;i<=m;i++) { x=map[vert[i].x][vert[i].y]; y=map[vert[i].x][vert[i].y+1]; if((vert[i].x+vert[i].y)%2==0) graphic[x][y]=1; else graphic[y][x]=1; } memset(match,-1,sizeof(match)); int ans=0; for(i=1;i<=nx;i++) { memset(vi,0,sizeof(vi)); if(dfs(i)) ans++; } printf("%d ",ans); } return 0; }