题意与分析
题意是这样的：给你一个\(N\times M\)的图，其中有一些点不能放置\(1\times 2\)大小的矩形，矩形可以横着放可以竖着放，问剩下的格子中，最多能够放多少个矩形。
注意到是\(1\times 2\)的矩形，所以是一个\(i+j\)和为奇数的可以与\(i+j\)为偶数的相连。抽象坐标和分别为奇数、偶数的为二分图的两个点集，可构建的矩形为边，那么剩下要做的就是二分图的最大匹配。
比较有趣的是具体实现。先把可以匹配的点单独拎出来，然后根据这些点建图。具体怎么建的呢？给每个可以匹配的点标记，如果这些点是奇数点，那么它周围的点连一条边。然后完事了。
然后如何打印结果呢？注意到Linker数组是保存了每一个点与其他点匹配的信息的，拿出来打印就是了。
这题重要的是这个奇偶的建图思想。
代码
/* ACM Code written by Sam X or his teammates.* Filename: hdu1507.cpp* Date: 2018-11-16*/#include <bits/stdc++.h>#define INF 0x3f3f3f3f
#define PB emplace_back
#define MP make_pair
#define fi first
#define se second
#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)
#define per(i,a,b) for(repType i=(a); i>=(b); --i)
#define ZERO(x) memset(x, 0, sizeof(x))
#define MS(x,y) memset(x, y, sizeof(x))
#define ALL(x) (x).begin(), (x).end()#define QUICKIO \ios::sync_with_stdio(false); \cin.tie(0); \cout.tie(0);
#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)using namespace std;
using pi=pair<int,int>;
using repType=int;
using ll=long long;
using ld=long double;
using ull=unsigned long long;int n,m,uN,vN;
int a[105][105], b[105], g[505][505];
bool used[505];
int linker[505];bool dfs(int u)
{rep(v,0,vN-1)if(g[u][v] && !used[v]){used[v]=true;if(linker[v]==-1 || dfs(linker[v])){linker[v]=u;return true;}}return false;
}int hungary()
{int res=0;MS(linker,-1);rep(u,0,uN-1){ZERO(used);if(dfs(u)) res++;}return res;
}int
main()
{while(cin>>n>>m){if(!n && !m) break;int k; cin>>k;ZERO(a);while(k--){int u,v; cin>>u>>v;a[u-1][v-1]=-1;}int idx=0;rep(i,0,n-1)rep(j,0,m-1){if(a[i][j]!=-1){b[idx]=i*m+j;a[i][j]=idx++;}}uN=vN=idx;ZERO(g);rep(i,0,n-1)rep(j,0,m-1){if(a[i][j]!=-1 && (i+j)%2){int u=a[i][j];if(i>0 && a[i-1][j]!=-1)g[u][a[i-1][j]]=1;if(i<n-1 && a[i+1][j]!=-1)g[u][a[i+1][j]]=1;if(j>0 && a[i][j-1]!=-1)g[u][a[i][j-1]]=1;if(j<m-1 && a[i][j+1]!=-1)g[u][a[i][j+1]]=1;}}int ans=hungary();cout<<ans<<endl;rep(i,0,vN-1){if(linker[i]!=-1){int x1=b[i]/m+1,y1=b[i]%m+1,x2=b[linker[i]]/m+1,y2=b[linker[i]]%m+1;cout<<"("<<x1<<","<<y1<<")--("<<x2<<","<<y2<<")\n";}}cout<<endl;}return 0;
}