随笔 - 11, 文章 - 0, 评论 - 12, 引用 - 0
数据加载中……

POJ 3686 The Windy's 拆点+KM

题目大意:
      有N个工件要在M个机器上加工,有一个N*M的矩阵描述其加工时间。
      同一时间内每个机器只能加工一个工件,问加工完所有工件后,使得平均加工时间最小。

   将工件作为二分图中X部的点,总共N个。
   将每个机器拆成N个点作为二分图中Y部的点,总共N*M个。
   第J个机器的第P个点代表,使用机器 J进行倒数第P次加工。
   假设我们按顺序在J机器上工件I1,I2,I3..IK个工件,则总共需要花费I1*K+I2*(K- 1)+I3*(K-3)++IK。
   所以我们对于X中每个点I,Y中每个点(J,P),连接一条A[I,J]*P权值的边。
   接下来进行二分图最佳匹配即可。这里有一篇介绍KM算法比较详细的文章:http://www.cnblogs.com/zhuangli/archive/2008/08/03/1259248.html

posted on 2010-05-04 21:30 acleast 阅读(432) 评论(0)  编辑 收藏 引用


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