给定一个棋盘，有些点是被删除的，问在这种情况下最多能够在这个棋盘中放置多少1*2的多米诺骨牌。
这题可以用二分图匹配来解决，将二维图复制出一份，将能够放置多米诺骨牌的两个相邻的点用边进行连接。如果采用邻接矩阵的话要开一个四维的数组G[x1][y1][x2][y2] 表示坐标为x1,y1 的点与x2,y2 的点之间是否放置一块多米诺骨牌。由于内存开不下，因此采用邻接表的形式来构造这些边。最后再求一个最大匹配即可。
代码如下（两个代码只是邻接表的实现不同）：
#include#include #include using namespace std;int N, M, cnt, dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1};int G[105][105], marry[10005], visit[10005];int head[10005];struct Node{ int num, next; // 相对于vector多出了一个指针变量next}e[40005];void buildedge(int x, int y){ e[cnt].num = y; e[cnt].next = head[x]; head[x] = cnt++; // 前插入 }bool judge(int x, int y){ if (x>=1&&x<=N&&y>=1&&y<=N) { return true; } else { return false; }}bool path(int u){ for (int i = head[u]; i != 0; i = e[i].next) { if (!visit[e[i].num]) { visit[e[i].num] = 1; if (!marry[e[i].num] || path(marry[e[i].num])) { marry[e[i].num] = u; return true; } } } return false; }int main(){ int x, y, sum, ans; while (scanf("%d %d", &N, &M) == 2) { sum = N*N, ans = 0, cnt = 1; // cnt 用来标记边的编号 memset(marry, 0, sizeof (marry)); memset(head, 0, sizeof (head)); // 这样已经假设0号边没有了意义 memset(G, 0, sizeof (G)); for (int i = 0; i < M; ++i) { scanf("%d %d", &x, &y); G[x][y] = 1; } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (!G[i][j]) { for (int k = 0; k < 4; ++k) { int xx = i+dir[k][0], yy = j+dir[k][1]; if (judge(xx, yy) && !G[xx][yy]) { buildedge((i-1)*N+j, (xx-1)*N+yy); // 前者指向后者 } } } } } for (int i = 1; i <= sum; ++i) { memset(visit, 0, sizeof (visit)); if (path(i)) { ++ans; } } printf("%d\n", ans>>1); } return 0; }
————————————————————————————————性感的分割线—-—————————————————————————————————
#include#include #include #include #include #define MAXN 105using namespace std;int N, M, sum, G[MAXN][MAXN], visit[10005], marry[10005];int dir[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0};vector v[10005];bool judge(int x, int y){ if (x>=1&&x<=N&&y>=1&&y<=N) { return true; } else { return false; }}bool path(int u){ vector ::iterator it; for (it = v[u].begin(); it != v[u].end(); ++it) { if (visit[*it]) { // 防止在递归过程中陷入死循环 continue; } else { visit[*it] = 1; // 表示对该点进行了测试 if (!marry[*it] || path(marry[*it])) { marry[*it] = u; return true; } } } return false;}int main(){ int x, y, ans; while (scanf("%d %d", &N, &M) == 2) { sum = N*N; ans = 0; memset(marry, 0, sizeof (marry)); memset(G, 0, sizeof (G)); for (int i = 1; i <= M; ++i) { scanf("%d %d", &x, &y); G[x][y] = 1; } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { v[(i-1)*N+j].clear(); // 清零 if (!G[i][j]) { // 说明这一点没有被删除 for (int k = 0; k < 4; ++k) { int xx = i+dir[k][0], yy = j+dir[k][1]; if (judge(xx, yy) && !G[xx][yy]) { // 只有位置合法后才去查看其值 v[(i-1)*N+j].push_back((xx-1)*N+yy); // 构建合理的边 // 将二维的点映射到一维数值上来 } } } } } for (int i = 1; i <= sum; ++i) { memset(visit, 0, sizeof (visit)); if (path(i)) { // path 函数就是寻找增广路径 ++ans; } } printf("%d\n", ans>>1); } return 0; }