个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
32
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++ 匈牙利算法案例分析详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法.
-------等等，看得头大？那么请看下面的版本:
通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异性有好感（-_-||暂时不考虑特殊的性取向），如果一对男女互有好感，那么你就可以把这一对撮合在一起，现在让我们无视掉所有的单相思（好忧伤的感觉），你拥有的大概就是下面这样一张关系图，每一条连线都表示互有好感.
本着救人一命，胜造七级浮屠的原则，你想要尽可能地撮合更多的情侣，匈牙利算法的工作模式会教你这样做:
一：先试着给1号男生找妹子，发现第一个和他相连的1号女生还名花无主，got it，连上一条蓝线 。
二：接着给2号男生找妹子，发现第一个和他相连的2号女生名花无主，got it 。
三：接下来是3号男生，很遗憾1号女生已经有主了，怎么办呢?
我们试着给之前1号女生匹配的男生（也就是1号男生）另外分配一个妹子.
(黄色表示这条边被临时拆掉) 。
与1号男生相连的第二个女生是2号女生，但是2号女生也有主了，怎么办呢？我们再试着给2号女生的原配重新找个妹子(注意这个步骤和上面是一样的，这是一个递归的过程) 。
此时发现2号男生还能找到3号女生，那么之前的问题迎刃而解了，回溯回去 。
2号男生可以找3号妹子~~~ 1号男生可以找2号妹子了~~~ 3号男生可以找1号妹子 。
所以第三步最后的结果就是:
四：接下来是4号男生，很遗憾，按照第三步的节奏我们没法给4号男生腾出来一个妹子，我们实在是无能为力了……香吉士同学走好.
这就是匈牙利算法的流程，其中找妹子是个递归的过程，最最关键的字就是“ 腾”字 。
其原则大概是：有机会上，没机会创造机会也要上 。
bool find(int x){ int i,j; for (j=1;j<=m;j++){ //扫描每个妹子 if (line[x][j]==true && used[j]==false) //如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了） { used[j]=1; if (girl[j]==0 || find(girl[j])) { //名花无主或者能腾出个位置来，这里使用递归 girl[j]=x; return true; } } } return false; }
在主程序我们这样做：每一步相当于我们上面描述的一二三四中的一步 。
for (i=1;i<=n;i++) { memset(used,0,sizeof(used)); //这个在每一步中清空 if find(i) all+=1; }
到此这篇关于C++ 匈牙利算法案例分析详解的文章就介绍到这了,更多相关C++ 匈牙利算法内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。
原文链接：https://blog.csdn.net/cillyb/article/details/55511666 。
最后此篇关于C++ 匈牙利算法案例分析详解的文章就讲到这里了,如果你想了解更多关于C++ 匈牙利算法案例分析详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
32
4
0
这个问题在这里已经有了答案: Oracle: merging two different queries into one, LIKE & IN (1 个回答) 8年前关闭。 我有以下代码: case
我查阅过此页面:http://dev.mysql.com/doc/refman/5.1/en/case.html以及这个，但无法获得一个简单的程序来工作...... 更新:为了明确我想要做什么:我想从
有什么办法可以优化下面的查询吗？ SELECT DATE_FORMAT(a.duedate,'%d-%b-%y') AS dte, duedate, SUM(CASE WHEN (typeofnoti
我进退两难，以下 SQL 查询的结果是什么以及它是如何工作的: SELECT ... CASE WHEN (a.FIELD=1 AND b.FIELD=2) THEN 1 WHEN
问题：输入年，月，打印对应年月的日历。 示例： 问题分析： 1，首先1970年是Unix系统诞生的时间，1970年成为Unix的元年，1970年1月1号是星期四，现在大多的手机的日历功能只能显
**摘要：**介绍了Angular中依赖注入是如何查找依赖，如何配置提供商，如何用限定和过滤作用的装饰器拿到想要的实例，进一步通过N个案例分析如何结合依赖注入的知识点来解决开发编程中会遇到的问题。 本
我想拥有自动伴侣类apply case 类的构造函数来为我执行隐式转换，但无法弄清楚如何这样做。我到处搜索，我能找到的最接近的答案是 this问题(我将解释为什么它不是我在下面寻找的)。 我有一个看起
您好，我已经浏览了“多列案例”问题，但没有看到与此相同的内容，所以我想我应该问一下。 基本上我有两个我想要连接的表(都是子查询的结果)。它们具有相同的列名称。如果我加入他们的 ID 和 SELECT
我发现了一些类型推断的非直觉行为。因此，语义等效代码的工作方式不同，具体取决于编译器推断出的有关函数返回类型的信息。当您在最小单元测试中重现此案例时，或多或少会清楚发生了什么。但我担心在编写框架代码时
CREATE TABLE test ( sts_id int , [status1] int , [status2] int , [status3] int , [status4] int ) INS
我有以下声明: SELECT Dag AS Dag, CASE Jaar WHEN 2013 THEN Levering END AS '2013', CASE
我想做的是为所有高于平均时间、平均时间和低于平均时间的游乐设施获取平均tip_portion。所以返回3行。当我运行它时，它显示: ERROR: missing FROM-clause entry
我正在尝试设置一个包含以下字段的报告: 非常需要报告来显示日期、该日期内的总记录(因此我按日期分组)，然后按小时计算 12 小时工作日(从上午 8 点到晚上 8 点)我需要计算记录在这些时间内出现的时
我有这个查询 SELECT users.name FROM users LEFT JOIN weapon_stats ON users.id = weapon_stats.zp_id WHERE we
我正在尝试按收视率等级获取不同视频的计数。我有下表: vid_id views 1 6 1 10 1 900 2 850 2 125000
假设我有一个如下所示的 SQL 语句: select supplier, case when platform in (5,6) then 'mobile' when p
我有一个表测试 TestNumber (int primary key) InactiveBitwise (int) 我执行以下命令: UPDATE tests SET CASE WH
我有一个像这样的表(name=expense): id amount date 1 -1687 2014-01-02 00:00:00.0 2 11000 2014-01-02 0
我有一个 multimap 定义 typedef std::pair au_pair; //vertices typedef std::pair acq_pair; //ch qlty specifi
我有一个有点像枚举的类，它的每个实例都有一个唯一的 int 值，该值从 0 开始并在每个新实例时递增。 class MyEnumLikeClass { static int NextId =
我是一名优秀的程序员,十分优秀！