【bzoj1070】[SCOI2007]修车

2014年5月1日5,21212

Description

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

Input

第一行有两个m,n,表示技术人员数与顾客数。 接下来n行,每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。

Output

最小平均等待时间,答案精确到小数点后2位。

Sample Input

2 2
3 2
1 4

Sample Output

1.50 

HINT

 

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

 

题解

没写cnt=1调了半天、、、

N辆车,M个工人。

 

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

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

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

 

为什么这么构图呢?

 

考虑第i个工人,他修第j辆车只对后面要修的车有影响,而前面修过的车已经对当前没有影响了。

而这个影响就是后面每个将要修理的车都多等待了time的时间。

 

其他边流量都为1是显然的,每辆车修一次,每个工人一个时段只能修理一辆车。

zkw快一些

 

  • TAT2015年3月14日 下午6:42 回复

    TAT为啥我觉得这道题的图可能有负环

    #1  
  • 3222015年3月14日 下午6:42 回复

    TAT为啥我觉得这道题的图可能有负环

    #2  
    • mxn2015年3月14日 下午8:53 回复

      这图没有环吧

      #21
      • 2332015年3月14日 下午8:55 回复

        考虑反向边

        #22
        • yyq2016年3月23日 下午8:53 回复

          应该没有,否则不满足消圈定理

          #23
  • 蒟蒻2016年2月5日 下午3:41 回复

    可是我不明白:这道题为什么必须让cnt=1?

    #3  
    • 2332016年3月24日 下午7:24 回复

      2333网络流的反向边啊

      #31
  • 糊涂2016年3月23日 上午9:55 回复

    请问题解中的(不是程序中)k是什么?

    #4  
  • 一个sb2016年4月15日 上午11:10 回复

    黄学长您t数组显然是开反了,,向我这种也开反了的那您的拍拍了一个小时还是挂啊

    #5  
  • 朱震霆2016年5月2日 下午5:26 回复

    啊……黄学长我有个问题啊……
    这个zkw费用流和普通费用流为什么看上去没啥区别啊……
    就是每次spfa算多条增广路吗…可是到T距离又不修改的话,不是只有几条最短路径不相交的时候才有优化吗……感觉和网上的zkw费用流完全不是一个风格(不过还是看不懂orz
    不过,讲道理的话距离真的不用修改吗……这样不会降低效率吗qwq

    #6  
    • hzwer2016年5月2日 下午8:29 回复
      admin

      其实。。。我从没看过网上的zkw费用流,是学长教我的,看起来就是改成了多路增广,有空我研究一下

      #61
      • 朱震霆2016年5月2日 下午8:34 回复

        哦哦……我网上的完全看不懂啊qwq

        #62