首页 > 题解 > bzoj 1070 [SCOI2007]修车

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)

题解

工人i修第j台车的时间为time(i,j),把每个工人拆成n个,对于工人i的第j个点表示工人i倒数第j个修的处理点,记为p(i,j);

S向每个人连容量为1、边权为0的边,对于第i个人,向(j,k)连容量为1、边权tim[j][i]*k的边,最小费用最大流即为答案。

因为我们难以确定一个点被其他点的“影响程度”,换个思路,考虑当前点对于别的点造成的影响,很容易发现,如果当前车在当前工人这里倒数第k个修理,那么对全局产生的贡献就是k*time,这样一来就可以直接处理每个点的贡献了。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×