The Windy’s
time limit per test 1 second memory limit per test 256 megabytes
The Windy’s is a world famous toy factory that owns M top-class workshop to make toys. This year the manager receives N orders for toys. The manager knows that every order will take different amount of hours in different workshops. More precisely, the i-th order will take Zij hours if the toys are making in the j-th workshop. Moreover, each order’s work must be wholly completed in the same workshop. And a workshop can not switch to another order until it has finished the previous one. The switch does not cost any time.

The manager wants to minimize the average of the finishing time of the N orders. Can you help him?

传送门:POJ3686

Input

The first line of input is the number of test case. The first line of each test case contains two integers, N and M (1 ≤ N,M ≤ 50). The next N lines each contain M integers, describing the matrix Zij (1 ≤ Zij ≤ 100,000) There is a blank line before each test case.

Output

For each test case output the answer on a single line. The result should be rounded to six decimal places.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3

3 4
100 100 100 1
99 99 99 1
98 98 98 1

3 4
1 100 100 100
99 1 99 99
98 98 1 98

3 4
1 100 100 100
1 99 99 99
98 1 98 98

Sample Output

1
2
3
2.000000
1.000000
1.333333

题解

很神奇的转化 练一下KM模板= = 用于求二分匹配中的权最大或最小
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
for(int o=1;o<=t;o++){
int n=sc.nextInt();
int m=sc.nextInt();
int[][]maze=new int[n+1][n*m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int shu=sc.nextInt();
for(int k=1;k<=n;k++){
maze[i][(j-1)*n+k]=-1*shu*k;
}
}
}
KM km=new KM(maze,n,n*m);
km.km();
pw.printf("%.6f",(km.sum()*-1.0)/n);
pw.println();
pw.flush();
}
}
}
class KM{
static int maxn=700;
int lx[]=new int[maxn],ly[]=new int[2580];
int Match[]=new int[2580];
int visx[]=new int[maxn],visy[]=new int[2580];
int slack[]=new int[2580];
int[][]w;
int INF=Integer.MAX_VALUE;
int ans,n,m;
KM(int[][] tu,int n,int m){
w=tu;
this.n=n;
this.m=m;
}
boolean findPath(int x)
{
int temp;
visx[x]=1;
for(int y=1; y<=m; y++)
{
if(visy[y]!=0)continue;
if(w[x][y]==lx[x]+ly[y])
{
visy[y]=1;
if(Match[y]==0||findPath(Match[y]))
{
Match[y]=x;
return true;
}
}
else
slack[y]=Math.min(slack[y],lx[x]+ly[y]-w[x][y]);
}
return false;
}
void km()
{
Arrays.fill(Match, 0);
Arrays.fill(lx, 0);
Arrays.fill(ly, 0);
for(int i=1; i<=n; i++)
{
lx[i]=-1;//if qiudeshizuixiao lx[i]=INF
}
for(int i=1;i<=m;i++){
ly[i]=0;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(lx[i]<w[i][j]) //if qiudeshizuixiao lx[i]>w[i][j]
lx[i]=Math.max(lx[i],w[i][j]);//
for(int x=1; x<=n; x++)
{
for(int i=1;i<=m;i++)
slack[i]=INF;
while(true)
{
Arrays.fill(visx, 0);
Arrays.fill(visy, 0);
if(findPath(x))break;
int tmp=INF;
for(int i=1;i<=m;i++)
{
if(visy[i]==0)
{
if(tmp>slack[i])
tmp=slack[i];
}
}
if(tmp==INF)return ;
for(int i=1; i<=n; i++)
{
if(visx[i]!=0) lx[i]-=tmp;//if qiudeshizuixiao lx[i]+=slack;
}
for(int i=1;i<=m;i++){
if(visy[i]!=0) ly[i]+=tmp;//ly[i]-=slack;
else
slack[i]-=tmp;
}
}
}
}
int sum(){
int max=0;
for(int i=1; i<=m; i++){
max+=w[Match[i]][i];
}
return max;
}
}