二分图匹配练习题
发布日期:2021-06-29 05:37:39
浏览次数:3
分类:技术文章
本文共 2808 字,大约阅读时间需要 9 分钟。
关于二分图匹配的讲解见文章。
本文练习两个简单的二分图匹配,分别对应于文章中的dfs和bfs的Hungary算法。
1、HDU1150
题意:两台机器A和B,每台都有许多工作模式。有多个任务,每个任务可以在A机器的某个模式或者在B机器的某个模式完成。问最少需要重启几次机器。
分析:该问题即最小点覆盖,即选取最少的点,使任意一条边至少有一个端点被选择,任务相当于边。最小点覆盖数=最大匹配数。
代码(dfs):
#include#include #define N 102int G[N][N];int matching[N], check[N];int n, m, k;bool dfs(int u){ for(int i = 1; i <= m; i++){ if(G[u][i]!=-1 && !check[i]){ check[i] = 1; if(matching[i] == -1 || dfs(matching[i])){ matching[i] = u; return true; } } } return false;}int main(){ while(scanf("%d", &n) && n){ scanf("%d%d", &m, &k); int a, b, c; memset(G, -1, sizeof(G)); for(int i = 0; i < k; i++){ scanf("%d%d%d", &a, &b, &c); if(b && c) G[b][c] = a; } int cnt = 0; memset(matching, -1, sizeof(matching)); for(int i = 1; i <= n; i++){ memset(check, 0, sizeof(check)); if(dfs(i)) cnt++; } printf("%d\n", cnt); } return 0;}
2、POJ2446
题意:给一个n*m的表格,表格中有一些格子挖去,用1*2或者2*1的长方形去覆盖,判断是否恰好完全覆盖。
解析:首先需要根据给定的图重新建图,然后求最大匹配数,如果剩余的格子的是最大匹配数的两倍,那么可以完全覆盖。
代码(bfs):
#include#include #include #include using namespace std;const int N = 32*32+5;int tol, k;int a[35][35];int pre[N], matching[N], check[N];vector G[N];queue Q;int nt[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}};bool Hungary(){ int ans = 0; memset(matching, -1, sizeof(matching)); memset(check, -1, sizeof(check)); for(int i = 1; i <= tol; i++){ if(matching[i] == -1){ while(!Q.empty())Q.pop(); Q.push(i); pre[i] = -1; bool flag = false; while(!Q.empty() && !flag){ int u = Q.front(); Q.pop(); for(int j = 0; j < G[u].size() && !flag; j++){ int v = G[u][j]; if(check[v] != i){ check[v] = i; Q.push(matching[v]); if(matching[v] != -1){ pre[matching[v]] = u; }else{ flag = true; int d = u, e = v; while(d != -1){ int t = matching[d]; matching[d] = e; matching[e] = d; d = pre[d]; e = t; } } } } } if(matching[i] != -1)ans++; } } if((tol - k) / 2 == ans)return true; return false;}int main(){ int x, y, n, m; while(~scanf("%d%d%d", &n, &m, &k)){ memset(a, 0, sizeof(a)); for(int i = 0; i < k; i++){ scanf("%d%d", &y, &x); a[x][y] = 1; } tol = n * m; if((tol - k) % 2){ printf("NO\n"); continue; } for(int i = 1; i <= tol; i++) G[i].clear(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ if(a[i][j] == 1)continue; int nw = (i-1)*m + j; for(int k = 0; k < 4; k++){ int nx = i + nt[k][0]; int ny = j + nt[k][1]; if(nx <= 0 || nx > n || ny <= 0 || ny > m)continue; if(a[nx][ny] == 1)continue; int p = (nx-1)*m + ny; G[nw].push_back(p); } } bool flag = Hungary(); if(flag)printf("YES\n"); else printf("NO\n"); } return 0;}
转载地址:https://blog.csdn.net/zhj_fly/article/details/75214103 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月17日 12时16分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
猿来绘Java-46-Collection接口及其方法
2019-04-29
猿来绘Java-47- foreatch 增强for循环
2019-04-29
2021/4/27课堂总结和作业
2019-04-29
2021.4.28课堂总结和作业
2019-04-29
2021.4.29课堂总结
2019-04-29
2021.4.30课堂总结和作业
2019-04-29
需要吗?2000GB+学习视频教程 面试资料免费下载
2019-04-29
MySQL对已存在数据库表添加自增ID字段
2019-04-29
idea中的一些常用快捷键
2019-04-29
js校验表单后提交表单的三种方法总结【转载】
2019-04-29
欢迎使用CSDN-markdown编辑器
2019-04-29
a标签中href调用js的几种方法
2019-04-29
jstl标签详解
2019-04-29
Eclipse中使用SVN的使用
2019-04-29
JSON.parse和eval的区别
2019-04-29
JQuery中$.ajax()方法参数详解
2019-04-29
正则表达式的数字实例
2019-04-29
OGNL表达式struts2标签“%,#,$”的区别
2019-04-29