首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >匈牙利算法

匈牙利算法

作者头像
用户1624346
发布2018-04-17 16:04:35
1.1K0
发布2018-04-17 16:04:35
举报
文章被收录于专栏:calmoundcalmound

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

此次总结依据实例进行,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 }

至此我们肯定

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2013-01-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档