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

poj_2195 Going Home(KM最佳匹配)

Posted on 2010-08-21 17:51 acronix 阅读(189) 评论(0)  编辑 收藏 引用 所属分类: hzshuai解题报告
题意:给一个n*m的方块矩阵,人和房子散乱的分布在上边,人数和房子数相等,现在要人都一动到房子里去,一人一房,人每一动一格花费为 1,问要全部人到达各自的房子的最少花费。

分析:转化为二分图最佳匹配,一边为人,一边为房子,他们之间的边权为负花费。再使用KM算法求得边权为负的最佳匹配,再取反极为最小花费了,轻松解决。

cpp代码:






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