题意：有N个工作，可以由M个工厂完成，但是每个工厂一次只能完成一个工作，并且完成这个工作之前不能换别的工作。问完成时间的平均值最少是多少。
思路：很神奇的建图，完全是突破天际了。
偶然间看到一种写法，突然感觉这个代码风格有点像魏神的，然后去他博客里一搜，居然真是。
来个传送门神牛博客
/*****以下转自上述博客********/
假设某个机器处理了k个玩具,那么对于这些玩具，有两种时间，一种是真正处理的时间，一种是等待的时间，等待的时间就是之前所有处理的玩具的时间，
假设这k个玩具真正用在加工的时间分为a1,a2,a3...ak, 那么每个玩具实际的时间是加工的时间+等待时间，分别为
a1, a1+a2, a1+a2+a3.......a1+a2+...ak
求和之后变为 a1 *k + a2 * (k - 1) + a3 * (k - 2).... + ak
这时就发现，每个玩具之间的实际时间可以分开来算 然后求和了。
因为对每个机器，最多可以处理n个玩具，所以可以拆成n个点，1~n分别代表某个玩具在这个机器上倒数第几个被加工的
所以我们对于每个玩具i，机器j中拆的每个点k，连接一条z[i][j]*k权值的边。
/******转完收工*******/
建完图就是最小权匹配了。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
/*********************************************/
#define N 2555
#define eps 1e-8
int n , m ;
int Map[55][N] ;
int lx[N] , ly[N] ,visx[N] , visy[N] , linkx[N] , linky[N] ;
//int fk[N][N] ;
int h ;
int find(int now) {
visx[now] = 1 ;
for (int i = 1 ; i <= h ; i ++ ) {
if(!visy[i] && Map[now][i] - lx[now] - ly[i] == 0) {
visy[i] = 1 ;
if(linky[i] == -1 || find(linky[i])) {
linkx[now] = i ;
linky[i] = now ;
return 1 ;
}
}
}
return 0 ;
}
int KM() {
mem(linky ,-1) ;
mem(ly , 0) ;
for (int i = 1 ; i <= n ; i ++ ) {
while(1) {
// bug ;
mem(visx, 0) ;mem(visy ,0) ;
if(find(i))break ;
int d = inf ;
for (int j = 1 ; j <= n ; j ++ )
if(visx[j])
for (int k = 1 ; k <= h ; k ++ )
if(!visy[k])
d = min(d , Map[j][k] - lx[j] - ly[k]) ;
for (int j = 1 ; j <= n ; j ++ ){
if(visx[j])lx[j] += d ;
}
for (int j = 1 ; j <= h ; j ++ ){
if(visy[j])ly[j] -= d ;
}
}
}
int ans = 0 ;
for (int i = 1 ; i <= h ; i ++ ){
if(linky[i] != -1)ans += Map[linky[i]][i] ;
}
return ans ;
}
int main() {
int t ;
cin >> t ;
while(t -- ) {
cin >> n >> m ;
mem(Map ,0) ;
int tt ;
for (int i = 1 ; i <= n ; i ++ ) {
for (int j = 1 ; j <= m ; j ++ ) {
scanf("%d",&tt) ;
for (int k = 1 ; k <= n ; k ++ ){
Map[i][n * (j - 1) + k] = k * (tt) ;
}
}
}
h = n * m ;
for (int i = 1 ; i <= n ; i ++ ){
lx[i] = inf ;
for (int j = 1 ; j <= h ; j ++ ){
lx[i] = min(lx[i] , Map[i][j]) ;
}
}
int ans = KM() ;
printf("%.6f\n",ans * 1.0 / n) ;
}
return 0 ;
}