posts - 64, comments - 4, trackbacks - 0, articles - 0

以下为KM算法模板:


同时BOJ 1084也是一个很裸的求二分图最佳匹配的问题。

Feedback

# re: KM最佳匹配的模板  回复  更多评论   

2012-05-25 09:59 by yuletianxia
您好,

读了您的博文受益良多。

在Boj 1080的中,你说,如果“求解最小权值完美匹配,可以将权值求相反数”。 我在这个地方有一些疑惑?

如果求相反数的话,可行顶标的修改步骤中d的取值是不是应该变为选最大?可行顶标的修改是不是S集合中点+d,而T集合中点-d? 还是仍然按照原始步骤即可?

另外,如果“求取最小权值完美匹配”,可不可以通过将权值取“倒数”的方法来实现。

初涉二分图匹配算法,万望博主不吝赐教

# re: KM最佳匹配的模板  回复  更多评论   

2012-05-25 10:01 by yuletianxia
貌似。boj2195就是最小权值完美匹配..

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理