时间限制：0.25s
空间限制：4M
题意:
给定一个N*N的棋盘，一些格子被移除，在棋盘上放置一些1*2的骨牌，判定能否放满，并且输出任意方案。
Solution：
首先考虑对棋盘的一个格子黑白染色（实际上不需要），得到一个类似国际象棋棋盘的东西，一个骨牌能放置在相邻的一对黑白格子上
我们考虑对每一个黑格子，连一条到相邻白色格子的边，然后做二分图的最大匹配，判断是否是完备匹配，输出解即可。
思路比较简单直接，输出需要一些简单技巧和小处理。
code
#include <iostream>
#include <cstring>
#include <fstream>
#include <cmath>
#include <cstdio>
using namespace std;
const int INF = ;
struct node {
int u, v, next;
} edge[];
int pHead[INF], vis[INF], pr[INF];
int dx[] = {, , , -}, dy[] = {, -, , };
int n, m, x, y, nCnt, an;
int exPath (int x) {
for (int k = pHead[x]; k != ; k = edge[k].next) {
int x = edge[k].u, y = edge[k].v;
if (!vis[y]) {
vis[y] = ;
if ( !pr[y] || exPath (pr[y]) ) return pr[y] = x;
}
}
return ;
}
void addEdge (int u, int v) {
edge[++nCnt].u = u, edge[nCnt].v = v;
edge[nCnt].next = pHead[u];
pHead[u] = nCnt;
}
int g[][];
int main() {
//ofstream cout("out.txt");
cin >> n >> m;
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++) g[i][j] = ;
for (int i = ; i <= m; i++) {
cin >> x >> y;
g[x][y] = ;
}
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++) {
if (g[i][j])
for (int k = ; k < ; k++) {
int x = i + dx[k], y = j + dy[k];
if (g[x][y])
addEdge ( (i - ) *n + j, (x - ) *n + y);
}
}
for (int i = ; i <= n * n; i++) {
if (exPath (i) ) an++;
memset (vis, , sizeof vis);
}
int t1 = , t2 = ;
int ans[][INF];
for (int i = ; i <= n * n; i++) {
if (pr[i] && !vis[i]) {
vis[i] = vis[pr[i]] = ;
if (abs (pr[i] - i) == n)
ans[][++t1] = min (i, pr[i]);
else
ans[][++t2] = min (i, pr[i]);
}
}
if (an == (n * n - m) ) {
cout << "Yes" << endl;
cout << t1 << endl;
for (int i = ; i <= t1; i++) {
int l, r;
if (ans[][i] % n) l = ans[][i] / n + , r = ans[][i] % n;
else
l = ans[][i] / n, r = n;
cout << l << ' ' << r << endl;
}
cout << t2 << endl;
for (int i = ; i <= t2; i++) {
int l, r;
l = ans[][i] / n + , r = ans[][i] % n;
cout << l << ' ' << r << endl;
}
}
else
cout << "No";
return ;
}