二分图最大匹配问题匈牙利算法
icon2 Program Impossible | icon4 2005-09-27 12:50| icon315 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

    研究了几个小时，终于明白了。说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。

Posted in Program Impossible
Tags: , , ,
Trackback: http://www.matrix67.com/blog/archives/39/trackback
我猜您可能还喜欢：

15 条回复

  • 楼层: 沙发 | 2007-04-15 19:51 | fearlessxjdx 说：

    大家弄个小数据模拟一下就能发现里面的奥秘了~
    真的很牛啊~

  • 楼层: 板凳 | 2007-04-15 19:55 | fearlessxjdx 说：

    不知道可不可以再扩展一个边(斜边)?
    那样是不是就变成N皇后问题了?

    回复：发错地方了？

  • 楼层: 地毯 | 2007-08-15 16:17 | kody_lau 说：

    说的还真是够白的，呵呵。

  • 楼层: 地板 | 2007-10-01 0:44 | 永恒的旋律 说：

    嗷~~~~~~~`
    为了研究这个匈牙利我n节课没好好听了！！
    结果还是没研究明白他工作原理~怒了  我要watch！！

  • 楼层: 地下室 | 2007-12-10 10:57 | dahe_1984 说：

    感谢matrix67,
    现在的教科书能不能写的简单直白点,
    别直接翻译老外的,写出来先自己看看能不能自己看明白,老子看了2天没看明白.

    再次感谢matrix67!!!

  • 楼层: 地基 | 2008-11-04 19:17 | memorygarden 说：

    赞一下，看了一下午没明白的地方，让您一点就明白了。谢谢您

  • 楼层: 地壳 | 2009-08-04 12:34 | Blue Gene 说：

    终于明白了……

  • 楼层: 地幔 | 2009-11-11 23:02 | dfx 说：

    简单的几句话 比别人几百句还清楚
    无比感激

  • 楼层: 地核 | 2010-02-01 13:09 | 小菜鸟 说：

    精简啊。。。现在我也明白了。。。orz

  • 楼层: 10楼 | 2011-03-22 10:59 | 【Graph】二分图 | Loong854.Snowing 说：

    [...] 二分图的最大匹配（匈牙利算法） [...]

  • 楼层: 11楼 | 2011-04-14 16:53 | 圣袭wgzly 说：

    很受用，谢谢！

  • 楼层: 12楼 | 2011-09-21 17:03 | 菜鸟 说：

    强大的楼主！ORZ！！

  • 楼层: 12a楼 | 2011-09-21 17:04 | 菜鸟 说：

    强大的楼主！ORZ

  • 楼层: 14楼 | 2012-01-31 19:17 | 弱菜 说：

    恍然大悟，膜拜神牛

  • 楼层: 15楼 | 2012-02-21 17:41 | POJ 1274 The Perfect Stall 解题报告 | ACShiryu 说：

    [...] 题目大意就是求二分图的最大匹配，算得上是基础题，直接运用匈牙利算法可以求解，关于匈牙利算法昨天找了一天资料，看了无数ppt都没有搞懂，那些讲解都太抽象了，直接文字表述，连个图都没有，现在也只是对该算法一知半解。匈牙利算法的思想说白了就是要你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。（传自Matrix67大牛的博客） [...]

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。