「BZOJ1070」[SCOI2007] 修车

2014年5月1日8,59412

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快一些

 

avatar
6 Comment threads
6 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
7 Comment authors
朱震霆hzwer一个sb233yyq Recent comment authors
  Subscribe  
提醒
朱震霆

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

一个sb
一个sb

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

糊涂

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

蒟蒻
蒟蒻

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

233
233

2333网络流的反向边啊

322
322

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

mxn
mxn

这图没有环吧

233
233

考虑反向边

yyq

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

TAT
TAT

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