#P2053. [SCOI2007] 修车

    ID: 1073 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>SPFA最大流网络流费用流各省省选2007四川

[SCOI2007] 修车

题目描述

同一时刻有 NN 位车主带着他们的爱车来到了汽车维修中心。

维修中心共有 MM 位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。

现在需要安排这 MM 位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。

说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入格式

第一行有两个数 M,NM,N,表示技术人员数与顾客数。

接下来 NN 行,每行 MM 个整数。第 i+1i+1 行第 jj 个数表示第 jj 位技术人员维修第 ii 辆车需要用的时间 Ti,jT_{i,j}

输出格式

最小平均等待时间,答案精确到小数点后 22 位。

2 2
3 2
1 4
1.50

提示

对于 100%100\% 的数据,2M92\le M\le 91N601\le N\le 601T1031\le T\le 10^3