h*******x 发帖数: 12808 | 1 求二分图的最小权值最大匹配(perfect匹配也行)的库。
哪里有这样的库啊?最好c/c++的。其他也语言也行,java,python,perl,lisp,
basic什么都行。
或者推荐一个容易实现的算法吧,谢谢了。
好像自己写太麻烦了。 |
M*****a 发帖数: 2054 | 2 匈牙利算法可以么?
【在 h*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 求二分图的最小权值最大匹配(perfect匹配也行)的库。 : 哪里有这样的库啊?最好c/c++的。其他也语言也行,java,python,perl,lisp, : basic什么都行。 : 或者推荐一个容易实现的算法吧,谢谢了。 : 好像自己写太麻烦了。
|
l******e 发帖数: 470 | 3 写个min-cost flow,也就100多行。
【在 h*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 求二分图的最小权值最大匹配(perfect匹配也行)的库。 : 哪里有这样的库啊?最好c/c++的。其他也语言也行,java,python,perl,lisp, : basic什么都行。 : 或者推荐一个容易实现的算法吧,谢谢了。 : 好像自己写太麻烦了。
|
l******e 发帖数: 470 | 4 这个是不带权的。
【在 M*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 匈牙利算法可以么?
|
h*******x 发帖数: 12808 | 5 我怎么记得匈牙利算法,是球二分图最大匹配的。
我想要的代权的二分图左右最大匹配中,权值最小的那个。
【在 M*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 匈牙利算法可以么?
|
h*******x 发帖数: 12808 | 6 谢谢,我研究研究。一会给你包
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写个min-cost flow,也就100多行。
|
h*******x 发帖数: 12808 | 7
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是不带权的。
|
h*******x 发帖数: 12808 | 8 转了你100个包子,谢谢了。
KM算法,这么基本的算法,我都忘记了,傻逼了我。
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写个min-cost flow,也就100多行。
|
h*******e 发帖数: 225 | 9 这个是带权的
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是不带权的。
|
h*******e 发帖数: 225 | 10 匈牙利算法就是干这个的
【在 h*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我怎么记得匈牙利算法,是球二分图最大匹配的。 : 我想要的代权的二分图左右最大匹配中,权值最小的那个。
|
|
|
h*******x 发帖数: 12808 | 11 呵呵,可能你记错了。
这个看你怎么说了,wiki上的匈牙利的算法,就是KM算法。
但我们一般提到的匈牙利算法,就是指求DFS求二分图最大匹配的算法。km的算法是用
顶标号+匈牙利算法求最优最大匹配。
【在 h*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 匈牙利算法就是干这个的
|
M*****a 发帖数: 2054 | 12 http://en.wikipedia.org/wiki/Hungarian_algorithm
看这个
【在 h*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呵呵,可能你记错了。 : 这个看你怎么说了,wiki上的匈牙利的算法,就是KM算法。 : 但我们一般提到的匈牙利算法,就是指求DFS求二分图最大匹配的算法。km的算法是用 : 顶标号+匈牙利算法求最优最大匹配。
|
l******e 发帖数: 470 | 13 一般匈牙利是指无权的。
网上km很多都有bug,要不根本就是算法理解错误,我记得我以前搜过,一个能用的没
找到
最后自己写了个mincost-flow了事,很容易写,比km应该容易写,而且速度不慢。
【在 M*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://en.wikipedia.org/wiki/Hungarian_algorithm : 看这个
|
h*******x 发帖数: 12808 | 14 请把我的留言第二段,反复阅读10遍
是用
【在 M*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://en.wikipedia.org/wiki/Hungarian_algorithm : 看这个
|
h*******e 发帖数: 225 | 15 所有我见过的literature里的Hungarian algorithm都是指带权的, 用来解决
assignment problem. 不知道你这个“我们一般提到。。。”是哪里来的,不信你可以
找个反例。
【在 h*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呵呵,可能你记错了。 : 这个看你怎么说了,wiki上的匈牙利的算法,就是KM算法。 : 但我们一般提到的匈牙利算法,就是指求DFS求二分图最大匹配的算法。km的算法是用 : 顶标号+匈牙利算法求最优最大匹配。
|
h*******x 发帖数: 12808 | 16 baidu,匈牙利算法
所有结果都是指不带权的
【在 h*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 所有我见过的literature里的Hungarian algorithm都是指带权的, 用来解决 : assignment problem. 不知道你这个“我们一般提到。。。”是哪里来的,不信你可以 : 找个反例。
|
M*****a 发帖数: 2054 | 17 你看过卢开澄的图论或者线性规划没有?
你去baidu一下
可以
【在 h*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : baidu,匈牙利算法 : 所有结果都是指不带权的
|
h*******x 发帖数: 12808 | 18 显然没有。
不然也不至于在这里丢脸问这么基础的问题。
【在 M*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你看过卢开澄的图论或者线性规划没有? : 你去baidu一下 : : 可以
|
M*****a 发帖数: 2054 | 19 不知道你的我们一般认为是哪里来的
topcoder 的算法tutorial
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
【在 h*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请把我的留言第二段,反复阅读10遍 : : 是用
|
h*******x 发帖数: 12808 | 20 百度 匈牙利算法
前几页。
为啥你从来不看我帖子就回复。
【在 M*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不知道你的我们一般认为是哪里来的 : topcoder 的算法tutorial : http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
|
|
|
l******e 发帖数: 470 | 21 话说卢的书还真是让人难以恭维
喜欢瞎起名字,写的一般,而且老有错误,我听过很多人complain他的书了。
【在 M*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你看过卢开澄的图论或者线性规划没有? : 你去baidu一下 : : 可以
|
M*****a 发帖数: 2054 | 22 这总比baidu前几页靠谱吧
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 话说卢的书还真是让人难以恭维 : 喜欢瞎起名字,写的一般,而且老有错误,我听过很多人complain他的书了。
|
h*******x 发帖数: 12808 | 23 我最后用的
http://blog.csdn.net/soberman/archive/2009/03/09/3974865.aspx
这个人写的KM算法,写的挺不错的。
这些算法都有标程的,找个NOI/ACM的网站,上面一大堆标程。
而且都是通过各种题目测试的。
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一般匈牙利是指无权的。 : 网上km很多都有bug,要不根本就是算法理解错误,我记得我以前搜过,一个能用的没 : 找到 : 最后自己写了个mincost-flow了事,很容易写,比km应该容易写,而且速度不慢。
|