题意
给出一个M＊N大小的棋盘(M,N都非常小)，棋盘上戳了几个洞，然后问你有没有可能用若干张1*2的骨牌，横着或者竖着填满整个棋盘，有洞的地方是不可以放置骨牌的。
思路
因为骨牌是1*2的，如果我们把整个棋盘看成一个图，每个没洞的地方都是一个节点，在棋盘上只要相邻（上下左右四联通）就可以看成两个节点有一条边相连，这样我们就可以发现，每一块骨牌正好就是图上的一条边。所以我们就把问题转化为了：给出一个图，要你用选出尽可能少的边，使得图上的每一个顶点都是选出的边中的某一条的端末，也就是“最小边覆盖”问题。
最小边覆盖=图中点的个数-最大匹配数=最大独立集
所以接下来的事情就很简单，按着上面的说法建图，然后运行一次最大匹配算法，之后作个差就搞定了。
还要注意一点，本题数据给出的形式可能和预想的不一样，挖洞的点是横坐标在前，纵坐标在后，如果WA，不妨检查一下是不是输入的时候做反了。
代码
本实现使用了匈牙利算法。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; #pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H) const int MAXN = 1050; const int INF = 0x3f3f3f3f; struct Node{ vector<int> to; } X[MAXN],Y[MAXN];//index starts from 0 int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y] bool ap_vis[MAXN];//vis marking array for augment path searching void init(){ for (int i = 0; i < MAXN; i++) { X[i].to.clear(); Y[i].to.clear(); } memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); } int ap_dfs(int u){ for (int i = 0; i < X[u].to.size(); i++) { int v = X[u].to[i]; if (!ap_vis[v]) { ap_vis[v] = true; if (matchY[v] == -1 || ap_dfs(matchY[v])) { matchX[u] = v; matchY[v] = u; return 1; } } } return 0; } int BGM_H(){ int ret = 0; memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); for (int i = 0; i < nx; i++) { if (matchX[i] == -1) { memset(ap_vis, false, sizeof(ap_vis)); ret += ap_dfs(i); } } return ret; } #pragma mark - bool board[40][40]; int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; inline int id(int y,int x,int m){ return (y-1)*m+x-1; } int main(){ int n,m,k; while (scanf(" %d %d %d",&n,&m,&k) != EOF) { memset(board, false, sizeof(false)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { board[i][j] = true; } } for (int i = 1; i <= k; i++) { int y,x; scanf(" %d %d",&x,&y); board[y][x] = false; } init(); int availPt = n*m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!board[i][j]) { availPt--; continue; } for (int d = 0; d < 4; d++) { int ny = i + dir[d][0]; int nx = j + dir[d][1]; if (board[ny][nx]) { X[id(i,j,m)].to.push_back(id(ny, nx, m)); Y[id(ny, nx, m)].to.push_back(id(i, j, m)); } } } } nx = ny = n*m; int res = BGM_H(); //cout << res << endl; if (res == availPt) { cout << "YES" << endl; }else{ cout << "NO" << endl; } } } |
