二分图匹配与带权匹配
2021/8/5 6:06:24
本文主要是介绍二分图匹配与带权匹配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分图最大匹配,二分图带权匹配
打第五场牛客多校的时候发现KM的板子复杂度假了,特来补上,顺带复习一下
二分图最大匹配
匈牙利算法
交替路:从一个未匹配点出发,依次经过非匹配边,匹配边,非匹配边\(\cdots\),形成的路径叫交替路。
增广路:途径交替路的起点之外的其他未匹配点的交替路叫做增广路。其一个重要性质是:非匹配边比匹配边多一条,因此交换增广路中的匹配边和非匹配边可以使匹配数+1。
增广路定理:当找不到增广路时,达到最大匹配。
匈牙利算法求最大匹配就是不断寻找增广路,每次找到增广路可以使匹配数+1,时间复杂度\(O(VE)\),空间复杂度\(O(E)\)
UOJ #78 二分图最大匹配:
#include<bits/stdc++.h> using namespace std; const int maxn = 1007; vector<int> adj[maxn]; bool vis[maxn]; //一次dfs过程中,右半边集合中的顶点是否已访问。 int ans[maxn], res[maxn]; //右半边集合中的点匹配的左半边点的编号。 int nl, nr, m; bool dfs(int u) { for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (!vis[v]) { //如果右半边的点v还未被访问 vis[v] = true; if (ans[v] == -1 || dfs(ans[v])) { //如果v没有匹配点,或是v的匹配点能找到一条到未匹配点的增广路 ans[v] = u; res[u] = v; return true; } } } return false; } int maxmatch() { int res = 0; memset(ans, -1, sizeof(ans)); for (int i = 1; i <= nl; i++) { memset(vis, 0, sizeof(vis)); res += dfs(i); } return res; } int main() { cin >> nl >> nr >> m; for (int i = 1; i <= m; i++) { int v, u; scanf("%d%d",&v,&u); adj[v].push_back(u); } printf("%d\n", maxmatch()); for (int i = 1; i <= nl; i++) { printf("%d ", res[i]); } return 0; }
HK算法
UOJ上的榜一写的Hopcroft-Krap算法,9msAC,,,时间复杂度\(O(\sqrt{V}E)\),实际速度很快
从hopcroft-karp算法 和二分图大讲堂——彻底搞定最大匹配数(最小覆盖数)、最大独立数、最小路径覆盖、带权最优匹配 - One thing I know,that is I know nothing.(Socrates Greek) - ITeye博客学习一波
HK算法的流程如下:
用bfs对图进行分层,左部点中的所有未匹配点组成第一层,把经过的匹配点全部加入队列,直到所有未访问的匹配点都加入队列。(bfs保证了不相交且最短)然后使用dfs遍历bfs找出的所有增广路(按层次走),每条增广路可以使匹配数+1.不断重复bfs和dfs,直到找出了增广路。
代码如下:
#include<bits/stdc++.h> using namespace std; const int maxn = 1007, inf = 0x3f3f3f3f; vector<int> adj[maxn]; int ansx[maxn], ansy[maxn], dx[maxn], dy[maxn], dis, nl, nr, m; //ansx,ansy储存的分别是左边点和右边点对应的匹配点,dx和dy是bfs分出的层次,dis是当前bfs的增广路的长度 bool vis[maxn]; bool bfs() { queue<int> q; dis = inf; memset(dx, -1, sizeof(dx)); memset(dy, -1, sizeof(dy)); //先找出左半边集合中的未匹配点作为bfs的源点 for (int i = 1; i <= nl; i++) { if (ansx[i] == -1) { q.push(i); dx[i] = 0; } } while (!q.empty()) { int u = q.front(); q.pop(); if (dx[u] > dis) break; for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (dy[v] == -1) { dy[v] = dx[u] + 1; if (ansy[v] == -1) dis = dy[v]; //每一轮bfs 增广路的长度+1 else { dx[ansy[v]] = dy[v] + 1; q.push(ansy[v]); } } } } return dis != inf; } bool dfs(int u) { for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (!vis[v] && dy[v] == dx[u] + 1) { vis[v] = 1; //if (ansy[v] != -1 || dy[v] == dis) continue; if (ansy[v] == -1 || (dy[v] != dis && dfs(ansy[v]))) { ansy[v] = u; ansx[u] = v; return true; } } } return false; } int maxmatch() { int res = 0; memset(ansx, -1, sizeof(ansx)); memset(ansy, -1, sizeof(ansy)); while (bfs()) { memset(vis, 0, sizeof(vis)); for (int i = 1; i <= nl; i++) { if (ansx[i] == -1) res += dfs(i); } } return res; } int main() { scanf("%d%d%d", &nl, &nr, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); } printf("%d\n", maxmatch()); for (int i = 1; i <= nl; i++) { printf("%d ", ansx[i] == -1 ? 0 : ansx[i]); } }
最大流
略,复杂度\(O(n^{0.5}m)\)
二分图带权匹配
费用流要注意spfa会被卡(牛客多校5 J),dijkstra费用流没去试,m=n^2时应该也好不到哪里去
正确写法的KM算法是严格\(O(n^3)\)的
AcWing 375. 蚂蚁 - O(n^3) DFS版 KM算法 - AcWing
lyd给的真\(O(n^3)\)的dfs版KM
KM(匈牙利)算法:
P6577 【模板】二分图最大权完美匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二分图最大权匹配 - OI Wiki (oi-wiki.org)
可以在\(O(n^3)\)的时间内求出二分图的最大权完美匹配;
这篇关于二分图匹配与带权匹配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)