📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5280| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

[树/链表/图] 二分图 匈牙利算法 python

🔗
tac20 | 只看该作者 |倒序浏览
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
适合小白,像我一样,刚刚接触匈牙利算法的刷友。
今天做1066 Campus Bikes II的时候接触到了匈牙利算法。然后google了半天,竟然没有发现python的版本。难受,只能自食其力,自己写一个,贴出来方便大家。
***************************
简单的稍微讲一下基本原理:
二分图:一个图,可以把所有顶点分成两个集合A,B,其中每条边都分别连接了A,B中的一个顶点
匹配:    边的集合,任意两条边都没有公共顶点。这些边交匹配边,剩下的边叫未匹配边
交错路:从一个未匹配点开始,依次经过未匹配边,匹配边,未匹配边。。。交替进行。这条路径叫交错路
増广路:如果交错路的最后一个顶点也是未匹配点,则为增广路。


下图中,明显a-e, d-g是匹配边。从h出发,黑色是未匹配边,红色是匹配边。这一条増广路。
不难发现,当调换红色黑色,原来的未匹配边为匹配边,我们发现匹配边的数量,比之前多了1.
下面是题目描述
***************************
过山车 HDU - 2063
RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了。可是,过山车的每一排只有两个座位,
而且还有条不成文的规矩,就是每个女生必须找个个男生做partner和她同坐。但是,每个女孩都有各自的想法,
举个例子把,Rabbit只愿意和XHD或PQK做partner,Grass只愿意和linle或LL做partner,PrincessSnow愿意和
水域浪子或伪酷儿做partner。考虑到经费问题,boss刘决定只让找到partner的人去坐过山车,其他的人,嘿嘿,
就站在下面看着吧。聪明的Acmer,你可以帮忙算算最多有多少对组合可以坐上过山车吗?
input: m = n = 3, arr = [[1,1],[1,2],[1,3],[2,1],[2,3],[3,1]]
***************************
接下来是python代码:
***************************
您好!
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies

*******************************
欢迎各路大神留言讨论

1.png (44.15 KB, 下载次数: 5)

1.png

评分

参与人数 4大米 +9 收起 理由
yeehaah + 5
PandasGZ + 2 很有用的信息!
Scala688 + 1 给你点个赞!
02cat + 1 给你点个赞!

查看全部评分


上一篇:Leetcode按投票数量排序的题目列表
下一篇:LeetCode: Facebook高频题,共250道,截至2019.12.31
推荐
codyman 2019-12-31 13:49:47 | 只看该作者
全局:
除了google不会有人问吧,而且这题可以用状态压缩的DP来解,不要求用匈牙利算法
回复

使用道具 举报

🔗
02cat 2019-12-31 12:49:22 | 只看该作者
全局:
棒棒哒!给你加米加米
回复

使用道具 举报

全局:
给lz点个赞
这种问题网络流也可以解,更快而且更通用
回复

使用道具 举报

全局:
面试真的有人被问networkflow的问题吗。。。
回复

使用道具 举报

🔗
 楼主| tac20 2020-1-1 02:47:37 | 只看该作者
全局:
ChitandaEru 发表于 2019-12-31 16:45
面试真的有人被问networkflow的问题吗。。。

感觉是不会的吧,但保不齐作为follow up让说一下思路
回复

使用道具 举报

🔗
mlwhut 2020-1-1 05:23:16 | 只看该作者
全局:
这道题的做法很多啊, backtracking, dp, min cost max flow, hungarian algorithm
回复

使用道具 举报

🔗
martinys 2020-1-2 14:57:41 | 只看该作者
本楼:
全局:
哇好厉害
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表