codevs2171 棋盘覆盖

codevs2171 棋盘覆盖

题目描述 Description 给出一张n*n(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。 输入描述 Input Description 第一行为n，m（表示有m个删除的格子）第二行到m+1行为x,y，分别表示删除格子所在的位置x为第x行y为第y列 输出描述 Output Description 一个数，即最大覆盖格数 样例输入 Sample Input 8 0 样例输出 Sample Output 32 数据范围及提示 Data Size & Hint 经典问题 分析：二分图匹配的经典问题，将原图进行二分图染色，黑色块与白色块相连，求出的最大匹配就是答案.因为是格子与格子连边，不能保证连完后是一个有向图，因此在匈牙利算法的时候要标记两次. 做这道题的时候因为粗心把int开成了bool,if后面直接跟了分号，气哭了QAQ. #include #include #include #include #include using namespace std; typedef vector::iterator iterator_t; int n, m, ans, pipei[10010]; int dx[] = { 0, -1, 0, 1 }, dy[] = { -1, 0, 1, 0 }; int flag[110][110],vis[10010]; int tot = 1, to[110010], nextt[100010], head[100010]; vector e[10010]; void add(int x, int y) { to[tot] = y; nextt[tot] = head[x]; head[x] = tot++; } bool judge(int x, int y) { if (x < 1 || x > n || y < 1 || y > n || flag[x][y]) return false; return true; } bool dfs(int u) { for (int i = head[u]; i;i = nextt[i]) { int v = to[i]; if (!vis[v]) { vis[v] = 1; if ((pipei[v] == -1)|| dfs(pipei[v])) { pipei[v] = u; pipei[u] = v; return true; } } } return false; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); flag[x][y] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (flag[i][j]) continue; for (int k = 0; k < 4; k++) { int nx = i + dx[k], ny = j + dy[k]; if (judge(nx,ny)) { int t1 = (i - 1) * n + j , t2 = (nx - 1) * n + ny; add(t1, t2); } } } } memset(pipei, -1, sizeof(pipei)); for (int i = 0; i < n * n; i++) { if (pipei[i] == -1) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ans++; } } printf("%d\n", ans); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。