主题

主题

 
   

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个人来找师傅,那么他所花费的等待时间就是Time[1]+Time[2]+……+Time[i]。

于是我们发现,把所有的和累加起来,总时间就是:

nTime[1]+(n-1)Time[2]+……+2Time[n-1]+Time[n]。

而这个Time是根据不同的维修序列来决定的。

于是我们建点:

对于第j个师傅,我们建立n个点,表示这个师傅是被安排在时间上第i个人找到去修车的。但是修的车不一定就是第i辆车。于是我们需要从每个点再想n辆车连一条边。

如果是安排在第1个人,那么这个时间的代价会计算n次,于是连向车的边的代价应该是原代价的n倍。同理,如果是安排在第二个人,那么这个时间的代价会计算n-1次,于是连向车的边的代价应该是原代价的n-1倍。以此类推。这样把真实的贡献计算出来了。

用图来解释,大概是这样:

(用cost[j][k]表示第j个师傅修第k辆车的(时间)花费)


接下来具体叙述建边的方法:

  1. 第k辆车 向 t 连一条<1/0>(<容量/费用>)的边。

  2. 建立n*m个点,其中每m个点划分为一类。

  3. s 向 第j类中第i个点 连一条<1/0>的边。

  4. 第j类中第i个点 向 第k辆车 连一条<1/cost[j][k]*(n-i+1)>的边。

之后我们跑最小费用流即可。

由于我们发现,其实同一类里面的点,地位是可以互换的。于是我们在“4”中,也可以改为

“第j类中第i个点 向 第k辆车 连一条<1/cost[j][k]*i>的边”


代码如下:

https://code.csdn.net/snippets/2144530

 
 
评论