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

poj_Machine Schedule(匈牙利算法初步)

Posted on 2010-08-21 13:34 acronix 阅读(190) 评论(0)  编辑 收藏 引用 所属分类: hzshuai解题报告
题意:就不多说了。

分析:(转的有图有真相吗)这个题目如果知道使用二分图的话就很简单了,关键就是如何构图。

依照题目意思能够构造出图(1),转变为图(2)之后发现,之前的job一定在图2中的某一条边上,同一条边上可以包含多个job,所以要完成所有的job,只需要包含所有的边即可,这就是最小点覆盖问题了。又知道二分图的最小点覆盖数=最大匹配数,因此可以用匈牙利算法求。(详细二分图关系见:)
cpp代码:


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