Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/10
08:54
费用流

[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)

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

费用流

首先把每个技术人员拆成n个点,表示第i个技术人员修的倒数第j辆车,考虑这辆车(假设为第k辆车)的影响,就是对于最后的j辆车,让他们都多等待了t[i,k]的时间。所以,

1、用每个拆出的点向每辆车连边(假设为第i个工人拆出的第j个点向第k辆车连边),容量为1费用为j*t[i,k]

2、从源点向每个拆出的点连边,容量为1,费用为0

3、从每辆车向汇点连边,容量为1,费用为0

最够跑一遍最小费用最大流,得到的结果就是等待时间和,最后/n就可以了

pascal:

c++:

 

[bzoj 1070] SCOI2007 修车