#P1070. [SCOI2007]修车

    ID: 73 传统题 1000ms 128MiB 尝试: 8068 已通过: 2260 难度: 7 上传者: 标签>CF2200提高+/省选-贡献法二分图建模指定流量最小费用流势能优化费用流Dijkstra残量网络费用流

[SCOI2007]修车

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

2 2
3 2
1 4

样例输出 #1

1.50

提示

对于 100%100\% 的数据,2≤M≤92\le M\le 9,1≤N≤601\le N\le 60,1≤T≤1031\le T\le 10^3。