匈牙利算法

今天学习了下匈牙利算法,发现这个早在几个月前学过的知识已经忘记的一干二净了,记得当初学习的时候只是看书,看论文,现在要好好的总结下,防止以后再次忘记。

此次总结依据实例进行,hdu2063

不同的女生喜欢的男生不一样,有可能喜欢的是同一个人,也有可能喜欢多个,至于谁和谁在一起男的说了没用,现在要求的是,如何搭配使数目达到最大

为了解决这个问题,我们先理解基本的两个概念

  • 交替路径(Alternating Path)是指这样一条路径,其中的每一条边交替地属于或不属于匹配 M。比如说,第一、三、五条边属于 M,而第二、四、六条不属于 M,等等。
  • 增广路径(Augmenting Path)是指从 M 中没有用到的顶点开始,并从 M 中没有用到的顶点结束的交替路径。

匈牙利算法也就是不断的通过找增广路径,来更新匹配数目,每增广一次,匹配数+1

下面分析这道题目,

6 3 3代表女生,男生的个数 1 1 1 2 1 3 2 1 2 3 3 1

首先

第一次匹配:1号女生和1号男生匹配

第二次匹配:2号女生找男生匹配,当她找到1号男生后,发现1号男生已经被1号女生霸占了,可是很遗憾,依据后来先得的道理,

1号女生不得不另外找个男生,把1号男生让给2号女生,很幸运1号女生找到了2号男生,2号女生找到了1号男生

第三次匹配:3号女生找男生匹配,发现她也喜欢1号男生,很遗憾,2号女生也只好换人了,幸运的2号女生找到了3号男生,

                 这样第三次匹配查找完毕

                1号女不变和3号男,2号女和3号男,3号女和一号男

至此大家肯定产生了疑问,假如说,在第二次匹配中,一号女找不带替代的男友怎么办,她甘心就这么给答案肯定是否定的,如果1号女找不到

替代的男友的话,她肯定不会将这个喜欢的男友让给后来的,这就相当于已经结婚了的女的,肯定不喜欢自己的丈夫被别的女孩子抢走。

我们可以看下面这组例子

假设1号女,2号女都喜欢1号男

1   1

2   1

在第一次匹配中1号女和1号男成功牵线,

在第二次匹配中2号女找1号男,由于1号女找不到替代的,所以此次匹配失败

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAXN=510;
 4 int pre[MAXN];//记录[i]男生属于谁
 5 int vis[MAXN];
 6 int map[MAXN][MAXN];
 7 int n,m;//男生,女生个数
 8 //匈牙利算法
 9 int find(int cur)//cur为当前女生
10 {
11     int i;
12     for(i=1;i<=m;i++)//被匹配的男生
13     {
14         if(map[cur][i] && !vis[i])//该男生未被匹配
15         {
16             vis[i]=true;//这次匹配中,该男生已经被匹配了
17             if(pre[i]==-1 || find(pre[i]))//该男生没有被匹配,或者被抢了的女生再去找一个男生
18             {
19                 pre[i]=cur;
20                 return 1;
21             }
22         }
23     }
24     return 0;
25 }
26 
27 int main()
28 {
29     int i,j,k;
30     int girl,boy;
31     int sum;
32     while(scanf("%d",&k) && k)
33     {
34         scanf("%d%d",&n,&m);
35         memset(pre,-1,sizeof(pre));
36         memset(map,0,sizeof(map));
37         for(i=0;i<k;i++)
38         {
39             scanf("%d%d",&girl,&boy);
40             map[girl][boy]=1;
41         }
42         sum=0;
43         for(i=1;i<=n;i++)//女生去匹配男生
44         {
45             memset(vis,0,sizeof(vis));//每次重新标记0
46             sum+=find(i);
47         }
48         printf("%d\n",sum);
49     }
50     return 0;
51 }

至此我们肯定

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程心路

从王者荣耀看设计模式-策略模式(java版)

曾经我也是一名玩农药的大学生,但现在已经弃了,别问我为什么(被坑爹队友坑的哭。。。)。而今天我们来把让农药变荣耀,我们来从王者荣耀中看设计模式的策略模式。

1665
来自专栏web前端教室

算法--天下武功,唯快不破

我只写JS,为什么也要学习算法? 我入行最开始时是做网页设计的,那是在2003年, 然后一路到了现在,... 所以做为读者的你应该已经明白,我是一个野路子出身的...

2175
来自专栏企鹅号快讯

C语言到底有多牛!你知道多吗?

有人说C语言是世界上最牛逼的语言,因为操作系统就是用C语言编写的,学好了C才能更好的学习其他编程语言。为此,有人分享了下面一段代码,说是很牛逼的c语言代码,看得...

56610
来自专栏Albert陈凯

Scala学习路线

这是一篇为公司内部”scala热情workshop”活动准备的文章,面向Scala初学者,目的在于帮助大家能尽早就建立起对Scala的整体认识,少走弯路。当然由...

6045
来自专栏诸葛青云的专栏

系统学习C语言方法大全

很多人对学习C语言感到无从下手,经常问我同一个问题:究竟怎样学习C语言?我是一个高级编程师,已经开发了很多年的程序,和很多刚刚起步的人一样,学习的第一个计算机语...

1460
来自专栏程序人生 阅读快乐

C++编程思想(两卷合订本)

《C++编程思想(两卷合订本)》曾荣获美国《软件开发》杂志评选的1996年jolt生产力大奖,中文版自2000年推出以来,经久不衰,获得了读者的充分肯定和高度评...

821
来自专栏我和PYTHON有个约会

23. 企业级开发基础4:面向对象

本节课程,概念为主~是为了后面的所有的开发进行一个理论性的铺垫,尽量总计的简单易懂,希望大家能耐心看完。

892
来自专栏鸿的学习笔记

关于英语,也许你忽视了很多东西

这是葛传椝老先生对英语学习者的教导,通篇用易读的英文短文讲述了英语学习过程中的种种心得,其中“大都是英语语法书和英语修辞学书不曾提到的”,文短而词丰,言简而意赅...

1001
来自专栏青青天空树

生理周期(c++实现)

描述:人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23 天、 28 天和33 天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面...

1052
来自专栏北京马哥教育

7个案例15分钟让你了解Python套路!

古人云:书山有路勤为径 学海无涯苦作舟 。 注:一般标榜着 “ XX天学会XX”、“ XX 分钟了解XX”的文章都不会是让你增长功力的文章,如本文。 随着互联...

3796

扫码关注云+社区

领取腾讯云代金券