Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1070: [SCOI2007]修车

题目链接

传送门

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)

想说的话

m,n读反了我调了两天你能信?

题解

费用流问题,把工人拆成N个点,表示N个时间段的工人。这样一共MxN个工人。
然后把N辆车和MxN个工人全部连起来(完全二分图),权值是工人时间段编号*输入的时间,表示需要等待的时间。
S到车流1费0,工人(MxN)到T流1费0。
这样加起来后满流的最小费用/N答案了。

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏