首页 > 其他 > 详细

[BZOJ1070][SCOI2007]修车(最小费用最大流)

时间:2015-01-01 00:10:29      阅读:293      评论:0      收藏:0      [点我收藏+]

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1070

分析:

把每个工人拆成N个点。记为A[i,j]表示第i个工人修倒数第j辆车。

每个车跟所有N*M个工人拆出的点连边。流量为1,费用为time[i,j]*k。

源和每辆车连边,N*M个点和汇连边,流量都为1,费用同为0。

 

为什么这么建呢?因为如果某个工人修了某辆车,那么只会对这个工人以后修的车的时间有影响,对已经修完的没影响,于是可以倒过来考虑。

[BZOJ1070][SCOI2007]修车(最小费用最大流)

原文:http://www.cnblogs.com/wmrv587/p/4196798.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!