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