匈牙利算法小讲
2021/7/13 22:36:16
本文主要是介绍匈牙利算法小讲,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
又名:匈牙利算法的封建
$ (bushi$
匈牙利增广路算法,简称匈牙利算法
原理:反转一条交错路径之后匹配边数\(+1\),找增广路
我们先来假设一个通篇都要用到的前提:
现在有 \(n\) 名男生, \(m\) 名女生。其中有 \(k\) 对男女互有好感,保证不出现gay或百合
一人不一定只有一个人与之配对(即一个女生可以与多个男生互有好感,反之亦然)。
若一对互有好感,那么我们作为中介可以让两人原地结婚。但是不可重婚,那是犯罪
好了,请问我们最多能撮合出最多几对夫妻呢?
那么显然,我们应用二分图的知识解决问题,方法如下图:
显然,假定男生们为主动方,如果他能找到的女生中有暂时没结婚的,就跟她结婚
但是我们会遇到一个问题:你得到的是否是最多对?
下图就是一个例子:
这时,我们所讲的匈牙利算法就派上用场了!
让我们以此图为例:
我们首先让 \(1\) 、 \(5\) 结婚,再给\(2\)介绍对象。
但我们经过查询发现: \(2\) 有一心仪对象 \(5\) 结了婚了!
我们再看一看 \(1\) ,发现他其实还可以和 \(6\) 结婚且 \(6\) 未婚。
邪恶的匈牙利算法便强制让 \(1\) 、 \(5\) 离婚以此给 \(2\) 找老婆!
太邪恶了!赤裸裸的包办婚姻!!!
再看 \(3\) ,却不曾想 \(3\) 有一心仪对象 \(6\) 结了婚了!
我们再看一看 \(1\) ,发现他其实和 \(5\) 还可以破镜重圆且 \(2\) 还可以和 \(7\) 结婚。
邪恶的匈牙利算法便又动了手脚:
\(1\)、\(5\)结婚,\(2\)、\(7\)结婚,\(3\)、\(6\)结婚
接下来到 \(4\) 了。很幸运,他可以直接和 \(8\) 结婚。
拆散婚姻什么的已经无所谓了,因为不再有姻缘,值得去拆了。——匈牙利算法
好了你已经掌握了匈牙利算法是个什么东西了。
接下来,也是最后一部分,就是喜闻乐见的上代码时间了:
(注:代码参考了我校一个老二刺猿学长 \(shadowice1984\),即 \(tbl\) 的 )
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=510; int n,m,e; int mp[N][N],match[N]; bool book[N]; bool dfs(int x){ for(int i=1;i<=m;i++){ if(book[i]||!mp[x][i]) continue; book[i]=true; if(match[i]==0||dfs(match[i])){ match[i]=x; return true; } } return false; } int main(){ scanf("%d%d%d",&n,&m,&e); for(int i=1;i<=e;i++){ int j;int k; scanf("%d%d",&j,&k); mp[j][k]=1; } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) book[j]=false; ans+=dfs(i); } printf("%d",ans); return 0; }
这篇关于匈牙利算法小讲的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南